[CS300 #055] 세그먼트 트리 — 구간 질의와 갱신을 모두 O(log n)

컴퓨터공학 300 주제 시리즈의 055번째 글이다. 전체 지도는 여기.

한 줄 요약

세그먼트 트리는 배열을 반씩 나눈 구간마다 합·최솟값 같은 요약값을 미리 저장한 이진 트리로, 원소 하나를 바꾸는 것과 임의 구간의 요약을 구하는 것을 모두 O(log n) 에 처리한다.

왜 필요한가

배열에 대해 “i 번부터 j 번까지의 합”을 자주 묻는다고 하자. 매번 더하면 O(n) 이다. 누적 합(prefix sum) 배열을 미리 만들어 두면 P[j] − P[i] 로 O(1) 에 답할 수 있다. 그런데 원소 하나가 바뀌면 그 뒤의 누적 합을 전부 고쳐야 하니 갱신이 O(n) 이다. 질의와 갱신이 섞여 들어오면 둘 중 하나는 반드시 느리다.

방법	구간 질의	점 갱신
그냥 배열	O(n)	O(1)
누적 합 배열	O(1)	O(n)
세그먼트 트리	O(log n)	O(log n)

세그먼트 트리는 둘 사이의 균형점이다. 게다가 합뿐 아니라 최솟값, 최댓값, 최대공약수, 행렬 곱처럼 결합 법칙이 성립하는 연산이면 무엇이든 다룰 수 있다. 누적 합은 빼기(역연산)가 있어야 쓸 수 있어서 최솟값에는 못 쓴다. 범위 최솟값 질의(RMQ) 자체가 하나의 연구 주제일 만큼 중요한 문제이며, 스탠퍼드 CS166 은 첫 강의를 이 문제에 쓴다(Stanford CS166 — Range Minimum Queries).

핵심 개념

구조

루트는 전체 구간 [0, n) 을 맡는다. 각 노드는 자기 구간을 반으로 나눠 두 자식에게 맡기고, 자기는 두 자식 값을 합친 값을 저장한다. 잎은 원소 하나다.

data = [5, 2, 8, 1, 9, 3, 7, 4]      (구간 합 트리)

                      [0,8) 39
                 /                \
          [0,4) 16                [4,8) 23
          /      \                /      \
     [0,2) 7   [2,4) 9      [4,6) 12   [6,8) 11
      /  \      /  \          /  \       /  \
     5    2    8    1        9    3     7    4

노드 수는 2n − 1 개 정도이고 높이는 ⌈log₂ n⌉ 이다. 메모리는 O(n) 이다.

구간 질의: 최대 O(log n) 개 노드로 덮기

[2, 6) 의 합을 구한다면, 이 구간을 트리 노드로 빈틈없이 덮는 조각을 찾는다. [2,4) 와 [4,6) 두 노드면 충분하다. 9 + 12 = 21. 일반적으로 어떤 구간이든 한 층에서 많아야 두 개 노드만 쓰므로, 전체로 O(log n) 개 노드를 합치면 답이 나온다.

질의 [2,6)                      ┌── 쓰는 노드
          [0,4)        [4,8)
         /    \       /    \
     [0,2) ▶[2,4)  ▶[4,6)  [6,8)

점 갱신: 잎에서 루트까지

data[3] 을 바꾸면, 그 잎과 조상들([2,4), [0,4), [0,8))만 다시 계산하면 된다. 경로 길이가 높이이므로 O(log n) 이다.

배열에 담기

힙과 같은 방식으로 배열에 담을 수 있다. 1번을 루트로 두면 노드 i 의 자식은 2i, 2i+1 이다. 이 글의 실습은 잎을 t[n:2n] 에 두고 내부 노드를 t[1:n] 에 두는 반복문 구현이다. 재귀 없이 아래에서 위로 올라가며 질의해 상수가 작다.

게으른 전파(lazy propagation)

“구간 [l, r) 의 모든 원소에 5를 더하라” 같은 구간 갱신은 잎을 하나씩 고치면 O(n) 이다. 게으른 전파는 구간을 덮는 O(log n) 개 노드에 “아래 자식들에게 아직 5를 안 더했음”이라는 메모만 붙여 두고, 나중에 그 아래로 내려갈 일이 생길 때 비로소 자식에게 넘긴다. 그러면 구간 갱신과 구간 질의가 모두 O(log n) 이 된다. 구현이 까다로워 버그가 잘 나는 부분이니, 아래 실습처럼 단순 계산과의 무작위 대조 테스트를 꼭 붙인다.

이름에 관한 주의

계산 기하학 교과서에서 말하는 “세그먼트 트리”는 선분(구간)들을 저장해 두고 어떤 점을 포함하는 선분을 모두 찾는 구조로, 이 글의 배열 구간 질의 구조와 이름은 같지만 목적이 다르다. 이 글의 구조는 경시 프로그래밍과 실무에서 흔히 같은 이름으로 부르는 쪽이다. 자료를 찾을 때 헷갈리지 않도록 알아 두면 좋다.

펜윅 트리와의 관계

다음 글의 펜윅 트리는 구간 합 문제를 더 적은 메모리(n 칸)와 더 짧은 코드로 푼다. 대신 역연산이 있는 연산(합)에 주로 쓰이고, 최솟값 같은 일반 구간 질의는 세그먼트 트리 쪽이 자연스럽다.

직접 해 보기

결합 연산을 인자로 받는 반복문 세그먼트 트리를 만든다. 같은 코드로 합, 최솟값, 최댓값 트리를 모두 만든다.

import random, operator

class SegmentTree:
    """반열린 구간 [l, r) 에 대한 결합 연산 질의. 배열 크기 2n, 반복문 구현."""
    def __init__(self, data, op, identity):
        self.n, self.op, self.e = len(data), op, identity
        self.t = [identity] * self.n + list(data)        # 잎은 t[n:2n]
        for i in range(self.n - 1, 0, -1):               # 부모 = 두 자식의 op
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, value):                          # 점 갱신: O(log n)
        i += self.n
        self.t[i] = value
        while i > 1:
            i //= 2
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):                               # 구간 [l, r): O(log n)
        resl, resr = self.e, self.e
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                resl = self.op(resl, self.t[l]); l += 1
            if r & 1:
                r -= 1; resr = self.op(self.t[r], resr)
            l //= 2; r //= 2
        return self.op(resl, resr)

data = [5, 2, 8, 1, 9, 3, 7, 4]
s = SegmentTree(data, operator.add, 0)
m = SegmentTree(data, min, float("inf"))
print("합 [2,6):", s.query(2, 6), "  최소 [2,6):", m.query(2, 6))
s.update(3, 10); m.update(3, 10)                         # data[3] = 1 → 10
print("갱신 후 합 [2,6):", s.query(2, 6), "  최소 [2,6):", m.query(2, 6))

# 무작위 검증: 단순 계산과 1만 번 대조
rng = random.Random(0)
arr = [rng.randint(-100, 100) for _ in range(300)]
st = SegmentTree(arr, max, float("-inf"))
for _ in range(10_000):
    if rng.random() < 0.5:
        i, v = rng.randrange(300), rng.randint(-100, 100)
        arr[i] = v; st.update(i, v)
    else:
        l = rng.randrange(300); r = rng.randint(l + 1, 300)
        assert st.query(l, r) == max(arr[l:r])
print("무작위 1만 연산 검증 통과")

합 [2,6): 21   최소 [2,6): 1
갱신 후 합 [2,6): 30   최소 [2,6): 3
무작위 1만 연산 검증 통과

구간 [2,6) 은 원소 8, 1, 9, 3 이라 합 21, 최소 1 이다. data[3] 을 10 으로 바꾸면 8, 10, 9, 3 이 되어 합 30, 최소 3 이다. 질의에서 왼쪽 결과 resl 과 오른쪽 결과 resr 을 따로 모으는 이유는 연산이 교환 법칙을 만족하지 않아도(예: 행렬 곱, 문자열 이어 붙이기) 순서를 지키기 위해서다. 크기 300 의 배열에 무작위 갱신과 질의를 1만 번 섞어 max(arr[l:r]) 와 대조했고 모두 일치했다.

현업에서는

시계열 구간 집계. “최근 1시간 중 임의 10분 구간의 최대 지연”처럼 시간 버킷 배열에 구간 최댓값·합을 반복해서 묻는 분석 코드에서, 버킷 값이 계속 갱신된다면 세그먼트 트리가 맞는다. 값이 고정이면 누적 합이나 희소 테이블이 더 단순하다.
자원 예약. 시간 축을 칸으로 나눈 예약 시스템에서 “이 구간에 남은 최소 용량”을 묻고 예약마다 구간에서 용량을 빼는 패턴은 게으른 전파가 있는 구간 최솟값 트리 문제다. 클러스터 스케줄러가 미래 시간대 자원 예약을 다룰 때 비슷한 구조가 필요하다.
선택 기준. 대부분의 실무 데이터는 데이터베이스가 집계해 준다. 세그먼트 트리를 직접 쓸 일은 “메모리 안에서, 갱신과 구간 질의가 둘 다 잦고, 지연 시간이 중요할 때”로 좁다. 그 조건이 아니면 더 단순한 방법을 먼저 고른다.
검증 습관. 실습처럼 단순한 O(n) 정답과 무작위 대조하는 테스트는 세그먼트 트리, 펜윅 트리, 게으른 전파처럼 경계 조건이 많은 구조를 다룰 때 가장 값싼 안전장치다.

확인 문제

누적 합 배열로는 구간 최솟값 질의를 O(1) 에 할 수 없는 이유는?
n = 8 인 세그먼트 트리에서 [1, 7) 질의에 쓰이는 노드 구간을 모두 적으라.
점 갱신이 O(log n) 인 이유는?
세그먼트 트리에 쓸 수 있는 연산의 조건은 무엇인가? 평균(mean)은 그대로 쓸 수 있는가?
게으른 전파가 해결하는 문제는?

풀이

누적 합은 P[j] − P[i] 처럼 역연산(빼기)으로 앞부분을 지워야 하는데, 최솟값에는 역연산이 없다.
[1,2), [2,4), [4,6), [6,7).
바뀐 잎의 조상만 다시 계산하면 되고, 그 수가 트리 높이 ⌈log₂ n⌉ 이다.
결합 법칙이 성립하고 항등원이 있어야 한다. 평균은 결합적이지 않으므로 그대로는 안 되고, (합, 개수) 쌍을 저장해 합친 뒤 나누면 된다.
구간 전체에 같은 갱신(더하기, 대입 등)을 적용하는 일을 잎마다 하지 않고, 구간을 덮는 노드에 미뤄 두었다가 필요할 때 내려보내 O(log n) 에 처리한다.

더 읽을거리 (References)

Stanford CS166 Data Structures, Lecture 00: Range Minimum Queries
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — Augmenting Data Structures 장
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008 — 10장 More Geometric Data Structures (기하학적 의미의 segment tree)