세그먼트 트리: 구간 결과를 합칠 수 있을 때의 자료구조
세그먼트 트리는 배열의 구간을 계층적으로 나누고 각 구간의 합, 최솟값 같은 결과를 저장한다. 원소 하나가 바뀌었을 때 모든 구간을 다시 계산하지 않고 그 원소를 포함하는 조상 구간만 갱신한다.
각 내부 노드는 담당 구간의 집계값을 저장한다.
결합 규칙이 구조를 만든다
루트는 전체 구간, 자식은 그 절반을 담당한다. 구간 합이라면 부모 값은 두 자식 합이고 구간 최솟값이라면 두 자식 중 작은 값이다. 어떤 방식으로 묶어도 같은 결과가 나오는 결합법칙과 빈 구간의 항등원이 필요하다.
아래 반복형 구현은 길이를 2의 거듭제곱으로 맞춘 구간 합 트리다. query(left,right)는 반열린 구간 [left,right)의 합을 반환한다.
size = 1
while size < len(values):
size *= 2
tree = [0] * (2 * size)
tree[size:size + len(values)] = values
for node in range(size - 1, 0, -1):
tree[node] = tree[2 * node] + tree[2 * node + 1]
def query(left, right):
left += size
right += size
result = 0
while left < right:
if left % 2 == 1:
result += tree[left]
left += 1
if right % 2 == 1:
right -= 1
result += tree[right]
left //= 2
right //= 2
return result
경계에 걸친 노드를 결과에 넣고 나머지를 부모 구간으로 올리므로 구간을 서로 겹치지 않는 몇 개 노드로 덮는다. 합은 교환법칙도 있지만 문자열 연결처럼 순서가 중요한 연산에는 왼쪽과 오른쪽 누적 결과를 나눠 결합해야 한다.
한 원소가 바뀌는 경로
[2,1,4,3]의 합은 10이다. 인덱스 1을 5로 바꾸면 해당 잎, [0,2) 구간, 전체 [0,4) 구간만 다시 계산해 전체 합을 14로 만든다. 다른 가지는 변하지 않는다.
초기 구성 시간 O(n), 저장 공간 O(n), 점 갱신과 구간 질의는 O(log n)이다. 크기를 가장 가까운 2의 거듭제곱으로 올려도 상수배 공간이다. 요청 범위가 배열 경계 안에 있는지는 별도로 검사한다.
구간 전체에 값을 더하는 갱신을 점 갱신으로 반복하면 느려진다. 지연 전파는 구간 변경 정보를 노드에 보류하여 이 작업을 확장하지만, 집계 값과 태그 결합을 정확히 설계해야 한다. 단순 합 트리에 어떤 변경도 붙일 수 있는 것은 아니다.
최솟값, 최댓값, 최대공약수 등에도 사용할 수 있지만 구간 중앙값처럼 두 결과만 간단히 합칠 수 없는 문제에는 추가 구조가 필요하다. 먼저 어떤 정보를 저장해야 자식의 결과로 부모의 결과를 계산할 수 있는지 확인하는 것이 세그먼트 트리 설계의 출발점이다.