펜윅 트리 (Fenwick Tree)
쉽게 풀면
펜윅 트리는 각 위치가 담당하는 구간의 크기를 그 인덱스의 이진수 표현에서 가장 오른쪽 1비트로 정합니다. 마치 잔돈을 낼 때 1000원, 100원, 10원짜리 지폐를 조합해서 정확한 금액을 맞추듯, 어떤 위치까지의 누적 합을 구할 때도 몇 개의 정해진 구간 값만 더하면 됩니다. 세그먼트 트리보다 구조가 단순해서 코드 몇 줄로 구현할 수 있는 것이 특징입니다.
왜 중요한가
많은 알고리즘 문제는 "값이 계속 바뀌는 배열에서 구간 합을 빠르게 구하라"는 형태로 귀결되며, 펜윅 트리는 이를 매우 적은 코드량으로 로그 시간에 해결합니다. 이 때문에 정렬·순위 계산, 역전 쌍(inversion count) 세기, 스트리밍 데이터의 누적 통계 처리 등 자료구조·알고리즘 논문에서 실험용 서브루틴으로 자주 채택됩니다. 구현이 간단하고 메모리 오버헤드가 작다는 점도 실용적 채택을 늘리는 이유입니다.
논문에서는 이렇게 쓰입니다
이 문장은 데이터가 계속 들어오면서 값이 갱신되는 상황에서도, "지금까지의 누적 합은 얼마인가"라는 질문에 빠르게 답하기 위해 펜윅 트리를 사용했다는 의미입니다. 순위 집계, 역전 쌍 계산, 스트리밍 통계 처리 등을 다루는 알고리즘 논문에서 자주 언급됩니다.
배열을 정렬할 때 원래 순서보다 뒤바뀐 쌍이 몇 개인지를 세는 문제로, 하나씩 비교하면 느리지만 펜윅 트리를 쓰면 원소를 하나씩 삽입하면서 누적 개수를 빠르게 조회할 수 있어 효율이 크게 개선됩니다.
데이터베이스나 시스템 로그처럼 끊임없이 새 이벤트가 들어오는 환경에서, 특정 시간 구간의 누적 횟수를 매번 전체를 다시 계산하지 않고도 즉시 답할 수 있도록 펜윅 트리를 온라인(실시간) 자료구조로 활용했다는 의미입니다.
조금 더 깊게 보면
펜윅 트리는 1차원 구간 합뿐 아니라 2차원 배열이나 다중 구간 갱신·구간 질의(range update, range query) 형태로 확장할 수 있으며, 이때는 보조 배열을 하나 더 두는 기법이 흔히 쓰입니다. 또한 값의 갱신과 조회 모두 인덱스의 이진 표현에서 최하위 1비트(lowbit, `i & -i`)를 반복적으로 더하거나 빼는 연산으로 구현되는데, 이 연산 하나가 트리를 순회하는 핵심 원리입니다. 논문에서 "BIT" 또는 "binary indexed tree"라는 표현으로도 자주 등장하므로 같은 자료구조를 가리킨다는 점을 알아두면 좋습니다.
주의할 점
펜윅 트리는 세그먼트 트리와 기능이 겹쳐 혼동되기 쉽지만, 펜윅 트리는 구간 합처럼 결합·역연산이 명확한 연산(덧셈 등)에는 강하지만 최댓값·최솟값처럼 역연산이 없는 질의는 세그먼트 트리만큼 자연스럽게 처리하지 못합니다.