Fenwick 트리 (Binary Indexed Tree, BIT)

Fenwick 트리 (Binary Indexed Tree, BIT)

배열의 구간 합(Prefix Sum)과 원소 갱신을 O(log n) 시간에 처리하는 간결한 트리 구조로, 세그먼트 트리보다 단순하고 메모리 효율적

목적: 구간 합 쿼리, 빠른 갱신, 메모리 효율, 동적 누적합

특징: 배열 기반, 비트 연산, 단순한 구현, 1-based 인덱스, 메모리 효율

핵심 아이디어: 각 인덱스는 2진수 표현의 마지막 1비트만큼의 구간 합 저장, LSB(Least Significant Bit) 활용

비트 연산: LSB(i) = i & (-i), 예: LSB(6) = 2, LSB(8) = 8

연산

• •update(idx, delta): idx에 delta 추가, 상위 노드로 전파, O(log n)
• •query(idx): [1, idx] 구간 합, 하위 노드 합산, O(log n)
• •rangeQuery(L, R): query(R) - query(L-1), O(log n)

동작

• •update: idx += LSB(idx) 반복하며 갱신
• •query: idx -= LSB(idx) 반복하며 합산

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

공간 복잡도: O(n)

장점: 단순한 구현, 메모리 효율(n), 빠른 연산(O(log n)), 비트 연산 활용

단점: 구간 합만 지원(최소/최대 어려움), 1-based 인덱스, 개념 이해 어려움

적용사례: 구간 합, 동적 누적합, 순위 쿼리, 역전 개수(Inversion Count)

비교: Fenwick(구간합/단순/n) vs 세그먼트 트리(다양연산/복잡/4n) vs 누적합(정적/O(1)쿼리)

연관: 세그먼트 트리, 구간 합, 누적합, 비트 연산