에듀테크 프로젝트 대시보드
세그먼트 트리 (Segment Tree)
배열의 구간 합을 매번 다 더하면 O(n) — 트리로 구간을 반씩 쪼개 저장하면 질의도, 수정도 O(log n)
"3번부터 9번까지 점수의 합은?" 같은 구간 질의(range query)를 자주 해야 한다고 하자. 배열을 그대로 두고 매번 for 문으로 더하면 한 번에 O(n)이다. 그런데 중간에 값이 자꾸 바뀐다면 누적 합(prefix sum) 배열도 매 수정마다 뒤쪽 전체를 다시 계산해야 해서 O(n)이 된다.
세그먼트 트리는 구간 [0, n-1]을 절반씩 재귀적으로 쪼개
각 노드에 "그 구간의 합"을 미리 저장해 둔 이진 트리다. 트리 높이가 ⌈log₂ n⌉이라
임의 구간 질의는 최대 2개의 경로로 O(log n), 한 원소 수정도 잎에서 뿌리까지 한 경로만 고쳐 O(log n)이다.
아래 배열의 칸을 클릭하면 값이 1씩 커지고(9 다음은 0), 잎에서 뿌리까지의 경로만 보라색으로 갱신된다.
슬라이더로 질의 구간 [L, R]를 고르고 구간 합 질의를 누르면,
그 구간을 빈틈없이 덮는 초록색 노드들만 골라 더하는 과정이 보인다.
# tree 크기는 넉넉하게 4*n. 노드 i의 자식은 2i, 2i+1 def build(node, lo, hi): if lo == hi: # 잎: 원소 하나 tree[node] = arr[lo] return mid = (lo + hi) // 2 build(2*node, lo, mid) build(2*node+1, mid + 1, hi) tree[node] = tree[2*node] + tree[2*node+1] def query(node, lo, hi, l, r): # [l, r] 구간 합 if r < lo or hi < l: # 완전히 벗어남 return 0 if l <= lo and hi <= r: # 완전히 포함 → 저장값 그대로 return tree[node] mid = (lo + hi) // 2 # 걸침 → 반씩 쪼개서 return query(2*node, lo, mid, l, r) \ + query(2*node+1, mid+1, hi, l, r) def update(node, lo, hi, idx, val): # arr[idx] = val if lo == hi: tree[node] = val return mid = (lo + hi) // 2 if idx <= mid: update(2*node, lo, mid, idx, val) else: update(2*node+1, mid+1, hi, idx, val) tree[node] = tree[2*node] + tree[2*node+1] # 올라오며 갱신
| 방법 | 구간 질의 | 지점 수정 | 메모 |
|---|---|---|---|
| 단순 배열 + 반복 | O(n) | O(1) | 질의가 드물면 충분 |
| 누적 합 (prefix sum) | O(1) | O(n) | 값이 안 바뀔 때 최고 |
| 펜윅 트리 (BIT) | O(log n) | O(log n) | 구현 짧음, 합 계열에 특화 |
| 세그먼트 트리 | O(log n) | O(log n) | 합·최솟값·GCD 등 아무거나, 구간 수정도 확장(lazy) |
경쟁 프로그래밍의 단골 도구이자, 실무에서도 "시간 구간별 집계", "리더보드 구간 순위", 게임의 충돌 판정용 구간 트리, DB의 구간 인덱스 아이디어의 바탕이 된다. 더하기 대신 min / max / gcd / 최대 부분합처럼 결합법칙이 성립하는 연산이면 무엇이든 같은 틀로 얹을 수 있다.