개념

구간 트리(세그먼트 트리, segment tree)는 배열의 연속 구간에 대한 질문, 예를 들어 "3번부터 7번까지의 합은?"이나 "이 구간의 최솟값은?"에 빠르게 답하면서, 배열 값이 바뀌어도 그 답을 빠르게 갱신할 수 있게 해 주는 자료 구조입니다. 이 장에서는 구간 트리가 왜 필요한지, 어떤 모양인지, 그리고 이후 장에서 계속 쓰일 용어를 정리합니다.

문제: 구간 질의와 갱신이 섞일 때

길이 n인 배열에 두 종류의 요청이 섞여서 많이 들어온다고 가정합니다.

• 점 갱신(point update): a[i]의 값을 바꿉니다.
• 구간 질의(range query): a[l]부터 a[r-1]까지의 합(또는 최솟값, 최댓값)을 구합니다.

가장 단순한 방법은 배열을 그대로 두고 질의마다 반복문을 도는 것입니다. 갱신은 O(1)이지만 질의는 O(n)입니다.

a = [5, 3, 7, 9, 6, 4, 1, 2]

def update(i, value):
    a[i] = value          # O(1)

def query(l, r):
    return sum(a[l:r])    # O(n): 구간 길이만큼 더한다

누적 합과의 비교

값이 바뀌지 않는다면 누적 합(prefix sum)이 가장 좋습니다. prefix[i]에 앞에서부터 i개 원소의 합을 저장해 두면 어떤 구간의 합이든 뺄셈 한 번으로 구할 수 있습니다. 하지만 원소 하나가 바뀌면 그 뒤의 누적 합을 모두 고쳐야 하므로 갱신이 O(n)이 됩니다.

from itertools import accumulate

a = [5, 3, 7, 9, 6, 4, 1, 2]
prefix = [0, *accumulate(a)]   # [0, 5, 8, 15, 24, 30, 34, 35, 37]

def query(l, r):
    return prefix[r] - prefix[l]   # O(1)

def update(i, value):
    diff = value - a[i]
    a[i] = value
    for k in range(i + 1, len(prefix)):   # O(n): 뒤쪽 누적 합을 모두 고친다
        prefix[k] += diff

print(query(2, 6))   # 26

구간 트리는 한쪽을 극단적으로 빠르게 만드는 대신 두 연산을 모두 `O(log n)`으로 맞춥니다. 요청이 수십만 개일 때 이 차이는 몇 초와 몇 시간의 차이가 됩니다.

구간 트리의 모양

구간 트리는 이진 트리입니다. 각 노드는 배열의 한 구간을 맡고, 그 구간의 요약 값(합, 최솟값 등)을 저장합니다.

• 루트는 전체 구간 [0, n)을 맡습니다.
• 어떤 노드가 [lo, hi)를 맡으면, 가운데 mid를 기준으로 왼쪽 자식은 [lo, mid), 오른쪽 자식은 [mid, hi)를 맡습니다.
• 리프(잎 노드)는 길이 1인 구간, 곧 원소 하나를 맡습니다.
• 내부 노드의 값은 두 자식 값을 합친 것입니다.

구간을 반씩 나누므로 트리의 높이는 약 log2 n입니다. 어떤 구간 질의든 이 트리에서 서로 겹치지 않는 노드 몇 개(한 층에 많아야 두 개)로 나누어 덮을 수 있고, 원소 하나를 바꾸면 리프에서 루트까지 한 경로만 다시 계산하면 됩니다. 이것이 두 연산이 모두 O(log n)인 이유입니다.

합치는 연산의 조건

구간 트리에 넣을 수 있는 연산은 결합 법칙을 만족해야 하고, 보통 항등원이 있으면 구현이 깔끔해집니다. 수학에서는 이런 구조를 모노이드(monoid)라고 부릅니다.

import math

# (합치는 함수, 항등원)
SUM = (lambda x, y: x + y, 0)
MIN = (min, math.inf)
MAX = (max, -math.inf)
GCD = (math.gcd, 0)
XOR = (lambda x, y: x ^ y, 0)

op, identity = MIN
print(op(op(4, 9), 2) == op(4, op(9, 2)))   # True: 결합 법칙
print(op(identity, 7))                      # 7: 항등원은 값을 바꾸지 않는다

반대로 "구간의 중앙값"처럼 두 자식의 요약 값만으로 부모 값을 만들 수 없는 질문은 기본 구간 트리로 풀 수 없습니다.

용어 정리

• 노드(node)와 구간(segment): 트리의 각 칸과 그 칸이 맡은 배열 범위입니다.
• 합치기(combine, merge): 두 자식 값을 부모 값으로 만드는 연산입니다.
• 항등원(identity): 질의 범위 밖의 노드가 돌려주는 중립 값입니다. 합은 0, 최솟값은 무한대입니다.
• 점 갱신과 구간 질의: 기본 구간 트리가 지원하는 두 연산입니다.
• 구간 갱신(range update): "구간 전체에 3을 더하라" 같은 요청입니다. 지연 전파(lazy propagation)로 처리합니다.
• 펜윅 트리(Fenwick tree, BIT): 합처럼 되돌릴 수 있는 연산에 특화된, 더 짧고 가벼운 대안입니다.

언제 쓰는가

• 배열 값이 자주 바뀌고, 그 사이사이에 구간 합 · 최솟값 · 최댓값을 물어볼 때
• 좌표를 정렬해 놓고 "이 값보다 작은 원소가 몇 개인가"를 반복해서 셀 때
• 스위핑(sweep line)으로 구간을 열고 닫으며 상태를 유지할 때

값이 전혀 바뀌지 않는다면 누적 합이나 희소 테이블(sparse table)이 더 단순하고 빠릅니다.

정리

구간 트리는 배열을 반씩 나눈 구간마다 요약 값을 저장해, 점 갱신과 구간 질의를 모두 O(log n)에 처리합니다. 합치는 연산이 결합 법칙을 만족하고 항등원이 있으면 합 · 최솟값 · 최댓값 · GCD 등 여러 질문에 같은 틀을 쓸 수 있습니다. 다음 장에서는 작은 배열로 트리를 직접 만들고 질의와 갱신을 따라가 봅니다.