구간 트리와 펜윅 트리는 코딩 테스트 단골 주제이지만, 실제 시스템에서도 "자주 바뀌는 수열에 대한 구간 요약"이 필요한 곳에 조용히 들어가 있습니다. 이 장에서는 쓰이는 곳, 바로 가져다 쓸 수 있는 라이브러리, 자주 하는 실수를 정리합니다.
쓰이는 곳
- 압축과 빈도표: 펜윅 트리는 원래 산술 부호화에서 기호의 누적 빈도를 빠르게 갱신하고 조회하려고 고안되었습니다. 기호가 나올 때마다 빈도를 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 누락 다섯 가지만 조심하면 대부분의 버그를 피할 수 있습니다.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.