실무 활용

구간 트리와 펜윅 트리는 코딩 테스트 단골 주제이지만, 실제 시스템에서도 "자주 바뀌는 수열에 대한 구간 요약"이 필요한 곳에 조용히 들어가 있습니다. 이 장에서는 쓰이는 곳, 바로 가져다 쓸 수 있는 라이브러리, 자주 하는 실수를 정리합니다.

쓰이는 곳

• 압축과 빈도표: 펜윅 트리는 원래 산술 부호화에서 기호의 누적 빈도를 빠르게 갱신하고 조회하려고 고안되었습니다. 기호가 나올 때마다 빈도를 1 늘리고, "이 기호 앞까지의 빈도 합"을 구하는 일이 반복되기 때문입니다.
• 순위표와 백분위: 점수별 인원을 펜윅 트리에 담아 두면 "내 점수보다 높은 사람 수", 곧 순위를 O(log n)에 구할 수 있습니다. 점수가 바뀌어도 해당 칸에서 빼고 더하면 됩니다.
• 시계열 모니터링: 분 단위 지표를 배열에 두고 "지난 구간의 최댓값 · 합계"를 반복해서 묻는 대시보드에서 구간 트리를 쓸 수 있습니다.
• 계산 기하: 직사각형 여러 개의 합집합 넓이처럼 스위핑으로 구간을 열고 닫는 문제는 "현재 덮인 길이"를 관리하는 구간 트리로 풉니다.
• 일정과 예약: 시간 칸마다 예약 수를 두고 "이 시간대의 최대 동시 예약 수"를 묻는 문제는 구간 더하기와 구간 최댓값을 지원하는 지연 전파 구간 트리로 풀 수 있습니다.

순위표 예시

class Leaderboard:
    """점수는 0..max_score 정수. 순위 = 나보다 점수가 높은 사람 수 + 1"""

    def __init__(self, max_score):
        self.size = max_score + 1
        self.tree = [0] * (self.size + 1)
        self.scores = {}

    def _add(self, score, delta):
        i = score + 1
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i

    def _count_at_most(self, score):
        i, total = score + 1, 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def set_score(self, player, score):
        if player in self.scores:
            self._add(self.scores[player], -1)
        self.scores[player] = score
        self._add(score, 1)

    def rank(self, player):
        higher = len(self.scores) - self._count_at_most(self.scores[player])
        return higher + 1


board = Leaderboard(1000)
for name, s in [("ana", 720), ("ben", 950), ("cho", 720), ("dev", 400)]:
    board.set_score(name, s)
print(board.rank("ana"), board.rank("ben"), board.rank("dev"))   # 2 1 4
board.set_score("dev", 990)
print(board.rank("dev"), board.rank("ben"))                      # 1 2

라이브러리

직접 짜는 대신 검증된 구현을 쓸 수도 있습니다. AtCoder Library(ACL)는 C++용 segtree, lazy_segtree, fenwick_tree를 제공합니다. 연산과 항등원을 함수로 넘기는 방식이라 앞에서 본 모노이드 개념과 그대로 맞물립니다.

#include <atcoder/segtree>
#include <climits>
#include <iostream>
#include <vector>

int op(int a, int b) { return a < b ? a : b; }   // 최솟값
int e() { return INT_MAX; }                        // 항등원

int main() {
    std::vector<int> v = {5, 3, 7, 9, 6, 4, 1, 2};
    atcoder::segtree<int, op, e> seg(v);
    std::cout << seg.prod(2, 6) << '\n';   // [2, 6)의 최솟값 4
    seg.set(4, 0);
    std::cout << seg.prod(2, 6) << '\n';   // 0
    std::cout << seg.all_prod() << '\n';   // 0
}

Python 표준 라이브러리에는 구간 트리가 없으므로, 보통 앞 장의 짧은 반복문 구현을 그대로 가져다 씁니다. 값이 바뀌지 않는다면 itertools.accumulate로 만든 누적 합으로 충분합니다.

자주 하는 실수

• 구간 끝 표기 혼동: [l, r](닫힌 구간)과 [l, r)(반열린 구간)을 섞으면 한 칸씩 어긋납니다. 한 가지로 정하고 함수 주석에 적어 둡니다.
• 잘못된 항등원: 최솟값 트리의 항등원을 0으로 두면 모든 값이 양수일 때 답이 0으로 나옵니다.
• 배열 크기: 재귀 구현에서 2n만 잡으면 n이 2의 거듭제곱이 아닐 때 인덱스가 넘칩니다. 4n을 잡습니다.
• 정수 넘침: C++과 Java에서 합을 int에 담으면 쉽게 넘칩니다. long long, long을 씁니다.
• push 누락: 지연 전파에서 자식으로 내려가기 전에 push를 부르지 않으면 이전 구간 갱신이 사라집니다.
• 펜윅 트리의 0번 인덱스: i & -i는 i = 0에서 0이므로 0번부터 쓰면 무한 반복에 빠집니다. 내부적으로 1부터 씁니다.

INF = float("inf")
values = [7, 3, 9]

def range_min(values, identity):
    best = identity
    for v in values:
        best = min(best, v)
    return best

print(range_min(values, 0))     # 0  (틀림: 항등원이 결과를 덮었다)
print(range_min(values, INF))   # 3  (맞음)

정리

구간 트리와 펜윅 트리는 빈도표, 순위표, 지표 집계, 스위핑 기하, 예약 관리처럼 바뀌는 수열을 구간 단위로 요약하는 곳에 쓰입니다. 구간 표기 · 항등원 · 배열 크기 · 정수 넘침 · push 누락 다섯 가지만 조심하면 대부분의 버그를 피할 수 있습니다.

더 읽을거리

• cp-algorithms: Segment Tree - 재귀 구현, 지연 전파, 다양한 변형을 자세히 다룹니다.
• cp-algorithms: Fenwick Tree - 펜윅 트리와 구간 갱신 변형입니다.
• Efficient and easy segment trees (Codeforces) - 이 문서의 반복문 구현과 같은 방식의 해설입니다.
• VisuAlgo: Segment Tree - 만들기와 질의를 애니메이션으로 보여 줍니다.
• AtCoder Library: Segtree - 연산과 항등원을 넘기는 범용 구간 트리 문서입니다.
• Wikipedia: Fenwick tree - 펜윅 트리의 역사와 정의입니다.