Fenwick Tree (펜윅 트리, Binary Indexed Tree)

Fenwick Tree (펜윅 트리, Binary Indexed Tree)

누적 합 계산과 점 갱신을 O(log n) 시간에 처리하는 트리 기반 자료구조로, Segment Tree보다 구현이 간단하고 메모리 효율적이며 이진 표현의 비트 연산 활용

목적: 빠른 누적 합, 점 갱신, 범위 합 쿼리

특징: O(log n) 쿼리/갱신, 메모리 O(n), 비트 연산, 구현 간단

핵심 아이디어: tree[i]는 구간 [i-LSB(i)+1, i] 합 저장, LSB=Least Significant Bit

LSB(i): i & -i, 예: LSB(12=1100₂) = 4=100₂

구축: O(n) 또는 O(n log n), 누적 합으로 초기화 또는 점 갱신 반복

점 갱신: 인덱스 i부터 i += LSB(i)로 이동하며 갱신, O(log n)

구간 합 쿼리: prefix_sum(r) - prefix_sum(l-1), prefix_sum(i) = 인덱스 i까지 합, i -= LSB(i)로 이동, O(log n)

시간 복잡도: 구축 O(n), 쿼리/갱신 O(log n)

공간 복잡도: O(n)

장점: 구현 간단, 메모리 효율, 빠름(상수 작음), 1-indexed 자연스러움

단점: 누적 합만 지원(최솟값 등 불가), 구간 갱신 어려움, 개념 이해 어려움

적용사례: 구간 합, 역전 쌍(Inversion Count), 순위 쿼리, 동적 중앙값

비교: Fenwick(log/합만/간단) vs Segment Tree(log/유연/복잡) vs 배열(n/단순)

연관: Segment Tree, 누적 합, 비트 연산, LSB, 구간 쿼리