세그먼트 트리(Segment Tree)는 배열의 구간(Range) 쿼리 를 효율적으로 처리하는 트리 자료구조다. 구간 합, 구간 최솟값/최댓값 쿼리를 O(log n)에, 업데이트도 O(log n)에 처리한다.
구조
배열: [1, 3, 5, 7, 9, 11]
인덱스: 0 1 2 3 4 5
세그먼트 트리 (구간 합):
[36]
/ \
[9] [27]
/ \ / \
[4] [5] [16] [11]
/ \ / \ / \
[1][3][5][7][9][11] (5]
구현
python
class SegmentTree:
def __init__(self, arr):
n = len(arr)
self.tree = [0] * (4 * n)
self.build(arr, 0, 0, n - 1)
def build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self.build(arr, 2*node+1, start, mid)
self.build(arr, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
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
return (self.query(2*node+1, start, mid, l, r) +
self.query(2*node+2, mid+1, end, l, r))
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
# 인덱스 1~3 구간 합: 3+5+7=15
관련 개념
참고문헌
- •Competitive Programming Handbook — Antti Laaksonen
