Fenwick Tree (Binary Indexed Tree): 구간 합 O(log N)

Fenwick 배열, Fenwick, Fenwick Tree, 펜윅 트리, BIT, Binary Indexed Tree, 이진 인덱스 트리, 펜윅

정의

Fenwick Tree (또는 BIT, Binary Indexed Tree) 는 배열의 prefix sum 을 O(log N) 에 갱신·조회 하는 자료구조입니다. Peter Fenwick 이 1994 년 발표.

핵심 아이디어: 각 인덱스가 자신의 lowbit 만큼의 구간을 담당 하도록 정의하여, prefix 합을 몇 개의 노드 값의 합으로 표현합니다.

왜 Segment Tree 대신 쓰는가

항목	Fenwick Tree	Segment Tree
코드 길이	매우 짧음 (10줄)	김 (30~50줄)
상수	매우 작음	큼
지원 연산	합, XOR 등 역연산 가능한 것	임의 결합 연산 (min, max, gcd)
구간 갱신	별도 트릭 필요	Lazy propagation 자연스럽게 지원

합 쿼리 위주라면 Fenwick 이 압도적입니다.

lowbit 연산

핵심은 x & -x (2의 보수 특성).

• x = 6 = 0110 → x & -x = 0010 = 2
• x = 12 = 1100 → x & -x = 0100 = 4
• x = 8 = 1000 → x & -x = 1000 = 8

의미: x 의 이진표현에서 가장 낮은 1 비트 만 남긴 값. 이것이 Fenwick 배열에서 그 인덱스가 담당하는 구간의 길이입니다.

구조

인덱스 i (1-based) 는 구간 $[i-\text{{}lowbit\}(i)+1,i]$ 의 합을 담당합니다.

i:  1 2 3 4 5 6 7 8
    │ ┴ │ ┴ ┴ ┴ │ ┴─────
    │   │       │       ┴
    ┴───┴───────┴───────
1 담당: [1,1]
2 담당: [1,2]
3 담당: [3,3]
4 담당: [1,4]
5 담당: [5,5]
6 담당: [5,6]
7 담당: [7,7]
8 담당: [1,8]

코드 (0-based 배열, 1-based Fenwick)

struct Fenwick {
    vector<long long> t;
    int n;

    Fenwick(int n) : n(n), t(n + 1, 0) {}

    void update(int i, long long v) {  // 1-based
        for (; i <= n; i += i & -i) t[i] += v;
    }

    long long query(int i) {  // 1-based, prefix [1..i]
        long long s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }

    long long range(int l, int r) {  // [l..r]
        return query(r) - query(l - 1);
    }
};

시간 복잡도: 두 연산 모두 O(log N).

Query 흐름 예 (N=8, query(6))

6 = 110

1. i=6 (110), t[6] 더함. i -= lowbit(6)=2 → i=4
2. i=4 (100), t[4] 더함. i -= lowbit(4)=4 → i=0
3. 종료.

prefix[6] = t[6] + t[4].

Update 흐름 예 (N=8, update(3, +5))

3 = 011

1. i=3 (011), t[3]+=5. i += lowbit(3)=1 → i=4
2. i=4 (100), t[4]+=5. i += lowbit(4)=4 → i=8
3. i=8 (1000), t[8]+=5. i += lowbit(8)=8 → i=16 > 8, 종료.

응용

1. 역수 세기 (Inversion Count)

배열 $a$ 에서 $i\text{<}j$ 지만 $a_i>a_j$ 인 쌍의 개수.

// a 를 오른쪽에서 왼쪽으로 순회
long long inv = 0;
Fenwick f(MAX_VALUE);
for (int i = n - 1; i >= 0; i--) {
    inv += f.query(a[i] - 1);   // 나보다 작은 값이 오른쪽에 몇 개?
    f.update(a[i], 1);
}

2. K-th 원소 (Fenwick 위 이분탐색)

값들에 카운트를 저장하고, prefix 합을 이분탐색으로 뒤져 k 번째 값 찾기. O(log² N).

3. 구간 갱신 + 점 쿼리 (차분 배열 트릭)

update(l, r, v):  fenwick.update(l, +v); fenwick.update(r+1, -v);
query(i):         fenwick.query(i)  // = a[i] 값

4. 구간 갱신 + 구간 쿼리 (Fenwick 2 개)

BIT 두 개 $B_1,B_2$ 로 임의 구간 갱신, 구간 합을 O(log N) 유지 가능.

2D Fenwick

2 차원 부분합에도 확장:

void update(int x, int y, long long v) {
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= m; j += j & -j)
            t[i][j] += v;
}

long long query(int x, int y) {
    long long s = 0;
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            s += t[i][j];
    return s;
}

O(log² N), 이미지/그리드 계열 문제에 유용.

함정

• 인덱스 시작: Fenwick 은 반드시 1-based. i > 0 종료 조건을 잊고 0-based 로 쓰면 무한 루프.
• 역연산 필요: range(l, r) = query(r) - query(l-1) 이 되려면 역연산 (뺄셈, XOR) 이 있어야 함. min/max 는 Fenwick 로 쿼리 불가 → Segment Tree 사용.
• 크기 제한: 좌표 압축 잊지 말 것. 값 범위가 크면 index 로 못 씀.

참고

• 관련 Segment Tree: 임의 연산 지원
• 관련 Prefix Sum: 정적 배열에 O(1) 쿼리
• 관련 Merge Sort Tree, Wavelet Tree: 더 복잡한 쿼리
• cp-algorithms: Fenwick Tree