펜윅트리

펜윅트리(Binary Indexed Tree, BIT)는 세그먼트트리와 같이 구간합을 구하고 값을 갱신하는 자료구조이다. 세그먼트트리보다 구현이 간단하고 메모리를 적게 사용한다.

각 인덱스가 담당하는 구간을 이진수의 마지막 1 비트(LSB) 를 이용해 결정한다. 인덱스 i가 담당하는 구간의 길이는 i & -i(lowest set bit)이다.

인덱스(이진)  담당 구간
1  (0001)  →  [1, 1]    길이 1
2  (0010)  →  [1, 2]    길이 2
3  (0011)  →  [3, 3]    길이 1
4  (0100)  →  [1, 4]    길이 4
5  (0101)  →  [5, 5]    길이 1
6  (0110)  →  [5, 6]    길이 2
7  (0111)  →  [7, 7]    길이 1
8  (1000)  →  [1, 8]    길이 8

prefix sum(1~i 구간합)은 i에서 시작해서 LSB를 빼며 올라가고, update(i번째 값에 v를 더함)는 i에서 시작해서 LSB를 더하며 올라간다. 두 연산 모두 O(log N)이다.

sum(7) = tree[7] + tree[6] + tree[4]
         (0111)    (0110)    (0100)

update(3) → tree[3], tree[4], tree[8] 갱신
             (0011)   (0100)   (1000)

https://www.acmicpc.net/problem/2042

#include <iostream>
using namespace std;

long long tree[1000001];
int n;

void update(int i, long long diff) {
    for (;i<=n;i+=i&-i) tree[i]+=diff;
}

long long sum(int i) {
    long long s=0;
    for (;i>0;i-=i&-i) s+=tree[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, k;
    cin>>n>>m>>k;

    vector<long long> arr(n+1);
    for (int i=1;i<=n;i++) {
        cin >> arr[i];
        update(i, arr[i]);
    }

    for (int i=0;i<m+k;i++) {
        int c, a;
        long long b;
        cin>>c>>a>>b;

        if (c==1) {
            update(a, b-arr[a]);
            arr[a]=b;
        } else {
            cout<<sum(b)-sum(a-1)<<'\n';
        }
    }
}

세그먼트트리와 비교하면, 메모리가 N으로 4N보다 적고 구현이 간단하지만, 구간 최솟값/최댓값 쿼리에는 적합하지 않다. 구간 업데이트 + 구간 쿼리를 하려면 트리를 2개 사용해야 한다.

펜윅트리는 역순쌍(inversion) 세기나, 증가 부분수열 개수를 세는 DP에서 prefix sum 쿼리를 빠르게 처리하기 위해 자주 사용된다.