ds · 12

세그먼트 트리

세그먼트트리구간쿼리트리

배열에서 "i번째부터 j번째까지의 합"을 구하고 싶을 때, 매번 구간을 훑으면 쿼리 한 번에 O(n)이 걸립니다. 값이 바뀌지 않는다면 누적 합 배열로 O(1)에 답할 수 있지만, 값이 중간에 자주 바뀌면 누적 합을 매번 다시 만들어야 해서 갱신이 O(n)이 됩니다. 세그먼트 트리(segment tree)는 구간 쿼리와 값 갱신을 모두 O(log n)에 처리하는 자료구조입니다.

배열 전체 구간을 절반씩 나누는 이진 트리를 만들고, 각 노드에 자기가 담당하는 구간의 합(또는 최솟값, 최댓값 같은 집계 값)을 미리 저장해 둡니다. 쿼리는 필요한 구간을 몇 개의 노드로 쪼개 저장된 값을 합치고, 갱신은 바뀐 원소에서 루트까지의 노드만 다시 계산합니다. 이 토픽에서는 트리를 만드는 과정, 구간 합 쿼리가 노드를 고르는 방법, 값 갱신이 퍼지는 경로를 단계별로 봅니다.

핵심 개념

구간 분할

루트가 전체 구간 [0, n - 1]을 담당하고, 각 노드는 구간을 반으로 나눠 두 자식에게 맡깁니다. 리프는 원소 하나짜리 구간을 담당하며, 높이(간선 수)는 ⌈log2 n⌉이고 층 수는 ⌈log2 n⌉ + 1입니다.

핵심 개념

집계 값 저장

각 노드는 담당 구간의 합, 최솟값, 최댓값 같은 집계 결과를 저장합니다. 부모의 값은 두 자식의 값을 합쳐서 만들기 때문에 구간 전체를 다시 훑을 필요가 없습니다.

핵심 개념

구간 쿼리

루트에서 내려가며 노드 구간이 찾는 구간과 겹치지 않으면 건너뛰고, 완전히 포함되면 저장된 값을 쓰고, 일부만 겹치면 두 자식으로 나눠 확인합니다.

핵심 개념

점 갱신

원소 하나를 바꾸면 그 원소를 포함하는 구간의 노드, 즉 리프에서 루트까지의 경로에 있는 노드만 두 자식의 합으로 다시 계산합니다.

핵심 개념

배열 표현

노드 i의 자식을 2i와 2i + 1에 두면 포인터 없이 배열로 트리를 저장할 수 있습니다. 재귀 구현에서는 n이 2의 거듭제곱이 아니어도 안전하도록 보통 4n 크기를 잡습니다.

핵심 개념

결합 법칙

두 자식의 결과를 합치는 연산이 결합 법칙을 만족하고 항등원이 있으면 세그먼트 트리에 쓸 수 있습니다. 합, 최솟값, 최댓값, 최대공약수 등이 대표적입니다.

쿼리와 갱신이 모두 O(log n)입니다 — 트리의 층 수가 log n에 비례하고, 한 번의 쿼리나 갱신이 층마다 일정한 수의 노드만 건드립니다. 만드는 데는 O(n)이 걸립니다.

누적 합과 비교해 값 변경에 강합니다 — 누적 합 배열은 쿼리가 O(1)이지만 값이 바뀌면 O(n)을 다시 계산해야 합니다. 세그먼트 트리는 두 연산을 O(log n)으로 맞춥니다.

저장 공간은 O(n)입니다 — 원소 n개에 노드가 약 2n개 필요합니다. 배열로 구현할 때 크기를 4n으로 넉넉히 잡는 것은 인덱스 안전을 위한 관례입니다.

구간 갱신에는 지연 전파가 필요합니다 — 구간 전체에 값을 더하는 갱신을 O(log n)에 하려면 변경을 나중으로 미루는 지연 전파(lazy propagation)를 씁니다. 이 토픽은 점 갱신까지 다룹니다.

이 시각화에서 확인할 것 — "트리 만들기" 탭에서 아래에서 위로 합이 쌓이는 과정을, "구간 합 쿼리" 탭에서 고르는 노드와 건너뛰는 노드를, "값 갱신" 탭에서 갱신이 번지는 경로를 STEP으로 확인하세요.

세그먼트 트리의 배경

세그먼트 트리라는 이름의 구조는 계산 기하학에서 나왔습니다. 1977년 카네기멜런대 기술 보고서에서 존 벤틀리(Jon Bentley)가 클리(Klee)의 직사각형 문제, 즉 직사각형들의 합집합 넓이를 구하는 문제를 풀며 소개한 것으로 알려져 있습니다. 원래의 구조는 구간(선분) 집합을 노드에 나눠 저장해 점 질의(stabbing)와 합집합 길이를 다룹니다. 이 토픽의 구간 합 트리는 노드에 구간의 집계 값을 저장한다는 같은 발상을 배열 구간 질의에 쓴 형태입니다. 펜윅 트리(BIT)는 같은 문제를 더 짧은 코드로 풀 수 있고, 세그먼트 트리는 합 이외의 연산과 지연 전파까지 다룰 수 있어 더 유연합니다.

숫자로 확인하기

트리 크기 — 배열 5, 8, 6, 3, 2, 7, 1, 4(원소 8개)로 만든 트리는 노드가 15개(= 2 × 8 - 1)이고 층이 4개(높이 3)입니다. 루트 값은 전체 합 36입니다.

구간 합 쿼리 — 구간 [2, 6]의 합은 6 + 3 + 2 + 7 + 1 = 19입니다. 노드 9개를 방문해 그 가운데 3개의 저장값(구간 [2, 3]은 9, [4, 5]는 9, [6, 6]은 1)만 더해 같은 값을 얻습니다.

값 갱신 — A[3]을 3에서 10으로 바꾸면 노드 4개(리프, 구간 [2, 3], [0, 3], [0, 7])만 다시 계산합니다. 구간 [2, 3]이 9에서 16으로, 전체 합이 36에서 43으로 바뀝니다.

규모의 차이 — 원소가 100만 개이면 층이 21개(높이 20)여서, 쿼리 한 번이 층마다 최대 4개씩 약 84개 이하의 노드만 방문합니다. 구간을 직접 훑으면 최대 100만 번을 더해야 합니다.

자주 하는 오해

쿼리가 구간 안의 모든 리프를 방문한다 — 완전히 포함된 구간은 저장된 값을 한 번 쓰고 더 내려가지 않습니다. 그래서 방문하는 노드가 구간 길이가 아니라 트리의 층 수에 비례합니다.

노드 수가 4n개다 — 실제 노드는 약 2n개이고, 4n은 재귀 구현에서 인덱스가 넘치지 않도록 잡는 배열 크기입니다. 반복형 구현은 2n으로 충분합니다.

합 전용 자료구조다 — 두 구간의 결과를 합치는 연산만 정의하면 최솟값, 최댓값, 최대공약수, 행렬 곱 같은 다른 집계에도 쓸 수 있습니다. 노드가 저장하는 값만 바꾸면 됩니다.

항상 세그먼트 트리가 최선이다 — 값이 바뀌지 않으면 누적 합이 더 단순하고 빠르고, 합과 점 갱신만 필요하면 펜윅 트리가 코드가 짧고 메모리를 덜 씁니다. 필요한 기능에 맞게 고릅니다.

면접에서 이렇게 물어요

면접 질문

세그먼트 트리는 언제, 왜 쓰나요?

값이 자주 바뀌는 배열에서 구간 합이나 구간 최솟값을 반복해서 구할 때 씁니다. 구간 쿼리와 값 갱신을 모두 O(log n)에 처리해, 직접 계산하는 O(n)이나 누적 합의 갱신 O(n)보다 유리합니다.

면접 질문

구간 쿼리는 어떻게 O(log n)이 되나요?

찾는 구간을 트리 노드 몇 개의 구간으로 쪼갭니다. 완전히 포함되는 노드의 저장값만 합치고 겹치지 않는 노드는 건너뛰므로, 한 층에서 방문하는 노드 수가 최대 4개로 제한되어 전체가 층 수에 비례합니다.

면접 질문

배열로 구현할 때 왜 4n 크기를 잡나요?

n이 2의 거듭제곱이 아니면 트리가 완전 이진 트리가 아니어서 노드 번호가 2n보다 커질 수 있습니다. 층 수가 ⌈log2 n⌉ + 1이라 최대 노드 번호가 2의 (⌈log2 n⌉ + 1)제곱 미만이고, 이 값은 4n보다 작으므로 4n이면 어떤 n에서도 넘치지 않습니다.

면접 질문

구간 전체에 값을 더하는 갱신은 어떻게 하나요?

지연 전파를 씁니다. 구간을 완전히 덮는 노드는 자기 집계 값(합이면 더하는 값 × 구간 길이)을 바로 갱신하고, 자식에게 줄 값은 "나중에 전달할 값"으로 표시만 해 둡니다. 그 노드를 지나 내려갈 때 비로소 자식에게 전달하므로 구간 갱신도 O(log n)에 처리합니다.

실제 시스템에서는

알고리즘 대회와 코딩 테스트 — 구간 합, 구간 최솟값, 구간 갱신 문제의 대표 해법입니다.

계산 기하 — 구간과 영역에 대한 질의를 처리하는 계산 기하 알고리즘의 부품으로 쓰입니다.

자료구조 확장 기법 — CLRS 14장(자료구조 확장)은 레드-블랙 트리 노드에 부분 트리 크기나 구간 끝점의 최댓값을 저장해 순위 질의와 구간 검색을 O(log n)에 하는 기법을 설명합니다. 노드에 요약값을 저장한다는 점에서 세그먼트 트리와 같은 발상입니다.

함께 보면 좋은 토픽

트리 — 높이, 깊이, 이진 트리의 기본 용어를 봅니다.

힙 — 배열 위에 완전 이진 트리를 올리는 같은 표현을 봅니다.

시간 복잡도 — O(log n)과 O(n)의 차이가 규모에 따라 벌어지는 방식을 봅니다.

이분 탐색 — 구간을 절반씩 줄여 가는 O(log n)의 원리를 봅니다.

참고 자료

교재 — de Berg 외, Computational Geometry: Algorithms and Applications, 3판(Springer, 2008), 10장 10.3 Segment Trees (구간 집합에 대한 점 질의용 구조로, 이 토픽의 구간 합 트리와는 쓰임이 다릅니다)

학습 자료 — cp-algorithms Segment Tree

기술 보고서 — J. L. Bentley, Klee의 직사각형 문제에 관한 카네기멜런대 컴퓨터과학과 기술 보고서(1977, 미출판)

Python — 재귀로 만드는 구간 합 세그먼트 트리

class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.t = [0] * (4 * self.n)             # 넉넉하게 4n
        self._build(1, 0, self.n - 1, arr)

    def _build(self, node, l, r, arr):
        if l == r:                            # 리프: 원소 하나
            self.t[node] = arr[l]
            return
        m = (l + r) // 2
        self._build(node * 2, l, m, arr)
        self._build(node * 2 + 1, m + 1, r, arr)
        self.t[node] = self.t[node * 2] + self.t[node * 2 + 1]

    def query(self, ql, qr, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if qr < l or r < ql:                # 겹치지 않음
            return 0
        if ql <= l and r <= qr:            # 완전히 포함: 저장된 값 사용
            return self.t[node]
        m = (l + r) // 2                    # 일부만 겹침: 둘로 나눔
        return (self.query(ql, qr, node * 2, l, m)
                + self.query(ql, qr, node * 2 + 1, m + 1, r))

    def update(self, idx, val, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if l == r:
            self.t[node] = val
            return
        m = (l + r) // 2
        if idx <= m:
            self.update(idx, val, node * 2, l, m)
        else:
            self.update(idx, val, node * 2 + 1, m + 1, r)
        self.t[node] = self.t[node * 2] + self.t[node * 2 + 1]   # 돌아오며 다시 계산

st = SegTree([5, 8, 6, 3, 2, 7, 1, 4])
print(st.query(2, 6))     # 19
st.update(3, 10)
print(st.query(2, 6))     # 26
print(st.query(0, 7))     # 43

노드 번호를 1부터 매기고 노드 i의 자식을 2i와 2i + 1로 두면 포인터 없이 배열 하나로 트리를 표현할 수 있습니다. 노드는 자기가 담당하는 구간 [l, r]을 재귀 호출의 인자로 들고 다닙니다. 배열 크기를 4n으로 잡는 것은 n이 2의 거듭제곱이 아니어도 인덱스가 넘치지 않게 하는 관례적인 여유입니다. query는 노드 구간이 찾는 구간과 겹치지 않으면 0을, 완전히 포함되면 저장된 값을 돌려주고, 일부만 겹치면 두 자식에게 나눠 맡깁니다. 이 세 경우가 시각화의 빨강, 초록, 노랑 노드에 해당하며 방문하는 노드 수가 O(log n)입니다. update는 리프 하나를 바꾼 뒤 재귀에서 돌아오며 경로의 부모 값만 두 자식의 합으로 다시 계산합니다. 시각화의 갱신 탭에서 구간 [2, 3]이 9에서 16으로, 전체 합이 36에서 43으로 바뀌는 것과 같은 결과이고, 코드의 쿼리 [2, 6] 합도 19에서 26으로 바뀝니다.

Python — 반복문으로 만드는 일반 세그먼트 트리

class Seg:
    def __init__(self, arr, op, ident):
        self.n, self.op, self.ident = len(arr), op, ident
        self.t = [ident] * self.n + list(arr)     # 리프는 n ~ 2n-1
        for i in range(self.n - 1, 0, -1):
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, val):
        i += self.n
        self.t[i] = val
        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)
        res = self.ident
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = self.op(res, self.t[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.op(res, self.t[r])
            l //= 2
            r //= 2
        return res

arr = [5, 8, 6, 3, 2, 7, 1, 4]
sums = Seg(arr, lambda a, b: a + b, 0)
mins = Seg(arr, min, float("inf"))
print(sums.query(2, 7), mins.query(2, 7))   # 19 1
mins.update(6, 9)
print(mins.query(2, 7))                   # 2

이 버전은 리프를 배열의 n번부터 2n - 1번에 두고, 위로 올라가며 두 자식의 결과를 합쳐 내부 노드를 채웁니다. 크기가 2n이면 충분하고 재귀가 없어 빠르며, 구간을 반개구간 [l, r)로 받아 아래에서 위로 올라가며 합칠 노드만 골라냅니다. 합치는 연산 op와 항등원 ident를 인자로 받으므로 같은 코드로 구간 합(항등원 0)과 구간 최솟값(항등원 무한대)을 모두 처리합니다. 구간 [2, 6]의 합은 19이고 최솟값은 1이며, A[6]을 9로 바꾸면 최솟값이 2가 됩니다. 이 반복형 query는 순서를 바꿔 합쳐도 결과가 같은(교환 법칙이 성립하는) 연산에 맞는 단순한 형태입니다. 문자열 이어붙이기나 행렬 곱처럼 교환 법칙이 안 되는 연산에는 왼쪽 결과와 오른쪽 결과를 따로 모아 순서대로 합치는 변형이 필요합니다.

Python — 무작위 입력으로 정답과 비교하기

import random

arr = [random.randint(1, 9) for _ in range(20)]
st = SegTree(arr)                      # 첫 번째 코드의 클래스
for _ in range(1000):
    if random.random() < 0.5:
        i, v = random.randrange(20), random.randint(1, 9)
        arr[i] = v
        st.update(i, v)
    else:
        l = random.randrange(20)
        r = random.randrange(l, 20)
        assert st.query(l, r) == sum(arr[l:r + 1])
print("ok")

자료구조를 직접 구현했다면 느리지만 확실한 방법(배열을 직접 더하는 sum)과 무작위로 비교해 보는 것이 가장 빠른 검증 방법입니다. 이 코드는 1000번의 연산을 평균적으로 절반쯤은 값 갱신, 나머지는 구간 합 쿼리로 섞어 두 결과가 항상 같은지 확인합니다. 쿼리 한 번의 비용은 배열 직접 합산이 구간 길이에 비례하는 O(n)이고 세그먼트 트리가 O(log n)입니다. 원소가 수십만 개이고 쿼리가 수십만 번이면 O(n × q)와 O(q log n)의 차이가 실행 시간을 가릅니다. 값이 바뀌지 않고 쿼리만 여러 번 한다면 누적 합 배열이 더 단순하고 빠르며, 값 갱신과 쿼리가 섞이는 상황에서 세그먼트 트리나 펜윅 트리가 필요해집니다.

세그먼트 트리에서 구간 쿼리와 값 갱신의 시간 복잡도는?

트리의 높이를 생각해 보세요.

세그먼트 트리는 구간을 절반씩 나눈 이진 트리 구조라 높이가 log n입니다. 쿼리와 갱신 모두 루트에서 리프까지의 경로 수준으로 처리해 O(log n)이 걸립니다.

세그먼트 트리의 각 노드가 저장하는 것은?

구간 합 트리라면 각 노드에 무엇이 있을까요?

각 노드는 자신이 담당하는 구간의 집계 결과(합, 최솟값, 최댓값 등)를 저장합니다. 부모 노드의 값은 두 자식의 값을 합쳐서 만듭니다.

배열 크기가 n일 때 세그먼트 트리를 배열로 구현하려면 보통 필요한 크기는?

n이 2의 거듭제곱이 아닐 때도 안전하게 잡는 여유값이 있습니다.

노드 i의 자식을 2i와 2i + 1에 두는 방식으로 배열에 저장하면, n이 2의 거듭제곱이 아닐 때 트리가 완전 이진 트리가 아니어서 노드 번호가 2n보다 커질 수 있습니다. 그래서 재귀 구현에서는 인덱스가 넘치지 않도록 보통 4n 크기로 잡습니다. 실제 노드는 약 2n개입니다.