樹狀數組 (Binary Indexed Tree)

學習 Binary Indexed Tree 前，建議先學會「前綴和與差分」此篇。

【名稱】Binary Indexed Tree(BIT)、Fenwick Tree、樹狀數組、二元索引樹。
【用途】單點修改、區間查詢。
【時間複雜度】O(log n)。
【特色】比線段樹快。

模板

#include <iostream>
using namespace std;
#define MAX 1005
#define lowbit(x) x&(-x)
int n, a[MAX];
void update(int i, int v){
    for(; i<=n; i+=lowbit(i))
        a[i] += v;
}
int query(int n){
    int sum = 0;
    for(int i=n; i>0; i-=lowbit(i))
        sum += a[i];
    return sum;
}
int main(){
    int i, v, l, r;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> v;
        update(i, v);
    }
    cin >> i >> v;
    update(i, v); //單點修改
    cin >> l >> r;
    cout << query(r)-query(l-1) << '\n'; //區間查詢
}

參考資料：WiwiHo的競程筆記