Ch.11 고급 자료구조
Segment Tree — 구간 쿼리의 마법
배열의 구간 합을 매번 O(n)으로 구한다고?
주식 데이터에서 '3번째~7번째 날의 최고가'를 반복 조회해야 합니다. 데이터가 수시로 바뀌는데, 매번 구간을 순회하면 너무 느립니다.
Prefix Sum은 업데이트가 O(n). 업데이트와 쿼리 모두 빠른 방법은?
Segment Tree는 build O(n), query O(log n), update O(log n) — 구간 쿼리의 만능 해결사입니다.
핵심 개념
Segment Tree
배열의 구간 정보를 트리로 관리하는 자료구조
구간 쿼리
배열의 [l, r] 범위에 대한 합/최솟값/최댓값 등을 구하는 연산
핵심 내용
구간 합을 구하는 방법들을 비교해봅시다
브루트포스: query O(n), update O(1) Prefix Sum: query O(1), update O(n) Segment Tree: query O(log n), update O(log n) ← 균형!
쿼리와 업데이트가 모두 빈번할 때 Segment Tree가 빛납니다
배열 [1, 3, 5, 7, 9, 11]의 Segment Tree를 그려봅시다
각 노드는 구간의 합을 저장합니다. 루트 = 전체 합, 리프 = 개별 원소
[36] ← [0,5] 전체 합 / \ [9] [27] ← [0,2] / [3,5] / \ / \ [4] [5] [16] [11] ← [0,1]/[2]/[3,4]/[5] / \ / \ [1] [3] [7] [9] ← 리프 노드
배열 크기 n일 때, 트리 크기는 4n으로 잡으면 안전합니다. 높이는 O(log n)
리프에 원소를 넣고 Bottom-up으로 부모를 채웁니다
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
return
mid = (start + end) // 2
self._build(arr, 2 * node, start, mid)
self._build(arr, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]재귀로 리프까지 내려간 뒤 올라오며 부모 = 왼쪽 자식 + 오른쪽 자식
[l, r] 구간 합을 구할 때 해당 구간을 커버하는 노드만 방문합니다
def query(self, l, r):
return self._query(1, 0, self.n - 1, l, r)
def _query(self, node, start, end, l, r):
if r < start or end < l: # 범위 밖
return 0
if l <= start and end <= r: # 완전히 포함
return self.tree[node]
mid = (start + end) // 2
left = self._query(2 * node, start, mid, l, r)
right = self._query(2 * node + 1, mid + 1, end, l, r)
return left + right3가지 경우 1. 현재 구간이 [l,r] 밖 → 0 반환 2. 현재 구간이 [l,r]에 완전 포함 → tree[node] 반환 3. 부분 겹침 → 양쪽 자식으로 분할 탐색
원소 하나를 바꾸면 해당 리프에서 루트까지 갱신합니다
def update(self, idx, val):
self._update(1, 0, self.n - 1, idx, val)
def _update(self, node, start, end, idx, val):
if start == end:
self.tree[node] = val
return
mid = (start + end) // 2
if idx <= mid:
self._update(2 * node, start, mid, idx, val)
else:
self._update(2 * node + 1, mid + 1, end, idx, val)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]리프 수정 → 부모 재계산 → ... → 루트까지. 높이가 O(log n)이므로 O(log n)
[1, 3, 5, 7, 9, 11]로 build → query(1,4) → update(2, 10)을 추적합니다
update 후 query 결과가 즉시 반영! Prefix Sum이라면 O(n) 재계산이 필요했을 것
합 외에도 최솟값, 최댓값, GCD 등 결합 연산이면 모두 적용 가능합니다
변형들 • Range Min/Max Query: merge를 min/max로 교체 • Lazy Propagation: 구간 업데이트를 O(log n)으로 • 2D Segment Tree: 행렬 구간 쿼리 면접 팁: 대부분 1D 구간 합/최솟값만 나옴. Lazy는 고급 면접만
Prefix Sum 대비 Segment Tree의 장점은?
Segment Tree의 build 시간 복잡도는?
Segment Tree에서 query 시 현재 구간이 [l,r]에 완전히 포함되면?
완전 포함 시 반환하는 값: tree[___]
핵심 용어
Segment Tree
구간 정보를 트리 노드에 저장, query/update O(log n)
구간 쿼리
[l, r] 범위의 합/최솟값/최댓값 등
build
O(n)
query
O(log n)
update
O(log n)
공간
O(4n) ≈ O(n)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작