펜윅 트리는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.
핵심은 Fenwick Tree의 원리와 사용 기준 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.
펜윅 트리 흐름을 그림으로 보기
펜윅 트리는 어떤 문제를 쉽게 만들까
펜윅 트리는 배열 값이 바뀌는 상황에서 누적합이나 구간 합을 빠르게 구하고 싶을 때 쓰는 자료구조입니다.
단순 prefix sum 배열은 조회는 빠르지만 중간 값이 바뀌면 뒤쪽 누적합을 많이 고쳐야 합니다. 반대로 펜윅 트리는 값을 하나 바꾸는 update와 prefix sum query를 둘 다 O(log n)에 처리합니다.
핵심은 구간 합을 직접 저장하는 것이 아니라 여러 크기의 누적 구간을 쪼개 저장하는 것입니다.
lowbit가 왜 중요할까
Fenwick Tree에서 `i & -i`는 현재 인덱스가 담당하는 구간의 크기를 알려줍니다. 예를 들어 12는 이진수로 1100이고, lowbit는 4입니다. 그래서 bit[12]는 끝이 12인 길이 4짜리 구간 합을 맡습니다.
i = 12 = 1100₂
lowbit(12) = 0100₂ = 4
bit[12] = a[9] + a[10] + a[11] + a[12]prefix sum query는 아래로 내려간다
prefixSum(i)는 i에서 시작해 lowbit만큼 왼쪽으로 이동하면서 필요한 구간들을 더합니다. 각 구간은 서로 겹치지 않고 1..i를 정확히 덮습니다.
long long prefixSum(int i) {
long long sum = 0;
while (i > 0) {
sum += bit[i];
i -= i & -i;
}
return sum;
}point update는 위로 올라간다
a[i]에 delta를 더하면, i를 포함하는 Fenwick node들을 모두 갱신해야 합니다. 이때는 `i += i & -i`로 다음 담당 구간으로 이동합니다.
void update(int i, long long delta) {
while (i <= n) {
bit[i] += delta;
i += i & -i;
}
}세그먼트 트리보다 언제 간단할까
구간 합과 단일 원소 업데이트만 필요하다면 Fenwick Tree가 세그먼트 트리보다 코드가 짧고 실수도 적습니다. 반면 구간 최소값, 최댓값, lazy propagation이 필요한 range update는 세그먼트 트리가 더 자연스럽습니다.
- 구간 합만 필요하면 Fenwick Tree를 먼저 검토한다
- 1-based indexing으로 구현해 lowbit 계산을 단순하게 만든다
- rangeSum(l, r)은 prefixSum(r) – prefixSum(l – 1)로 만든다
- 최솟값/최댓값/복잡한 merge가 필요하면 세그먼트 트리를 고려한다
- 좌표 값이 크고 개수만 적으면 좌표 압축과 함께 쓴다
정리
펜윅 트리는 세그먼트 트리의 하위 호환이 아닙니다. 대신 구간 합과 point update처럼 목적이 좁은 문제에서는 더 짧고 빠르게 구현할 수 있는 좋은 선택지입니다. lowbit가 담당 구간의 크기를 알려준다는 점만 잡으면 구조가 훨씬 선명해집니다.
관련 글로는 누적합과 차분 배열, 좌표 압축은 언제 필요할까, 자바 ArrayList와 LinkedList 차이을 함께 보면 좋습니다. 외부 기준은 Baeldung – Fenwick Tree, Codeforces – Fenwick Tree, OI Wiki – Fenwick Tree을 확인했습니다.
