동작 원리

이 장에서는 배열 a = [5, 3, 7, 9, 6, 4, 1, 2] 하나로 구간 트리를 만들고, 구간 합 질의와 점 갱신이 트리 안에서 어떻게 움직이는지 한 단계씩 따라갑니다. 이어서 반복문으로 아래에서 위로 도는 방식과, 구간 전체를 바꾸는 지연 전파의 개념도 살펴봅니다.

1단계: 트리 만들기

노드 번호를 1부터 매기고, 노드 k의 자식을 2k, 2k+1로 두는 방식이 가장 흔합니다. 리프에 원소를 놓고, 위로 올라가며 두 자식의 합을 부모에 씁니다.

                 [0,8) 37
           /                  \
      [0,4) 24              [4,8) 13
      /      \              /      \
  [0,2) 8  [2,4) 16    [4,6) 10  [6,8) 3
   /  \     /  \        /  \      /  \
  5    3   7    9      6    4    1    2

노드는 모두 2n - 1개이고, 각 노드를 한 번씩 계산하므로 만드는 데 O(n)이 듭니다.

2단계: 구간 질의 [2, 6)

a[2] + a[3] + a[4] + a[5]를 구합니다. 루트에서 출발해 각 노드에서 세 경우 중 하나를 고릅니다.

• 노드 구간이 질의 구간과 겹치지 않으면 항등원 0을 돌려줍니다.
• 노드 구간이 질의 구간 안에 완전히 들어가면 저장된 값을 그대로 돌려줍니다.
• 일부만 겹치면 두 자식에게 내려가 결과를 더합니다.

답은 26이고, 실제로 7 + 9 + 6 + 4 = 26입니다. 질의 구간은 [2,4)와 [4,6) 두 노드로 나뉘어 덮였습니다. 각 층에서 "일부 겹침"으로 내려가는 노드는 많아야 두 개이므로 방문하는 노드 수는 O(log n)입니다.

3단계: 점 갱신 a[3] = 0

a[3]이 9에서 0으로 바뀌면 리프 [3,4)를 고치고, 그 조상만 다시 계산합니다.

• [3,4): 9 → 0
• [2,4): 16 → 7 + 0 = 7
• [0,4): 24 → 8 + 7 = 15
• [0,8): 37 → 15 + 13 = 28

리프에서 루트까지 한 경로, 곧 log2 8 + 1 = 4개 노드만 바뀌었습니다. 이 과정을 재귀 함수로 그대로 옮기면 다음과 같습니다.

a = [5, 3, 7, 9, 6, 4, 1, 2]
n = len(a)
tree = [0] * (4 * n)

def build(node, lo, hi):
    if hi - lo == 1:
        tree[node] = a[lo]
        return
    mid = (lo + hi) // 2
    build(2 * node, lo, mid)
    build(2 * node + 1, mid, hi)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(node, lo, hi, 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, hi, l, r)

def update(node, lo, hi, i, value):
    if hi - lo == 1:
        tree[node] = value
        return
    mid = (lo + hi) // 2
    if i < mid:
        update(2 * node, lo, mid, i, value)
    else:
        update(2 * node + 1, mid, hi, i, value)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

build(1, 0, n)
print(query(1, 0, n, 2, 6))   # 26
update(1, 0, n, 3, 0)
print(query(1, 0, n, 2, 6))   # 17

n이 2의 거듭제곱이 아니면 트리가 한쪽으로 조금 기울기 때문에, 안전하게 배열 크기를 4n으로 잡습니다.

반복문 방식: 아래에서 위로

재귀 없이도 같은 일을 할 수 있습니다. 크기 2n인 배열의 뒤쪽 절반 tree[n..2n)에 원소를 놓고, i = n-1부터 1까지 tree[i] = tree[2i] + tree[2i+1]을 계산합니다. 질의는 양 끝 lo = l + n, hi = r + n에서 출발해 부모로 올라가면서, 경계에 걸친 노드만 결과에 더합니다.

a = [5, 3, 7, 9, 6, 4, 1, 2]
n = len(a)
tree = [0] * n + a
for i in range(n - 1, 0, -1):
    tree[i] = tree[2 * i] + tree[2 * i + 1]

lo, hi, total = 2 + n, 6 + n, 0
while lo < hi:
    if lo & 1:                 # lo가 오른쪽 자식이면 그 노드를 쓰고 오른쪽으로
        total += tree[lo]; lo += 1
    if hi & 1:                 # hi가 오른쪽 자식이면 왼쪽 이웃을 쓴다
        hi -= 1; total += tree[hi]
    print(f"lo={lo} hi={hi} total={total}")
    lo //= 2; hi //= 2
print(total)                   # 26

구간 갱신과 지연 전파

"[0,4)의 모든 원소에 2를 더하라"를 점 갱신 네 번으로 처리하면 O(k log n)이 듭니다. 지연 전파(lazy propagation)는 구간을 완전히 덮는 노드에서 멈추고, 그 노드에 "자식들에게 아직 2를 더하지 않았다"는 메모(lazy 값)를 남깁니다.

구간 [0,4)에 +2
  [0,4): 24 + 2 * 4 = 32, lazy = 2   (자식은 아직 그대로)
  [0,8): 32 + 13 = 45

나중에 질의 [2,4)가 [0,4)를 지나 내려갈 때 메모를 자식에게 넘긴다(push)
  [0,2): 8 + 2 * 2 = 12, lazy = 2
  [2,4): 16 + 2 * 2 = 20, lazy = 2
  [0,4): lazy = 0

메모는 그 노드 아래로 내려갈 일이 생길 때만 처리되므로 구간 갱신도 O(log n)에 끝납니다. 구체적인 코드는 연습 문제 장에서 다룹니다.

정리

구간 트리는 반씩 나눈 구간마다 합을 저장해 두고, 질의는 겹침 여부에 따라 내려가며, 갱신은 리프에서 루트까지 한 경로만 다시 계산합니다. 반복문 방식은 크기 2n 배열로 같은 일을 더 짧게 하고, 지연 전파는 구간 갱신을 미뤄 두었다가 필요할 때 자식에게 넘깁니다.