學習 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的競程筆記