- 【用途】計算動態「前綴和」，比線段樹更節省記憶體，也更容易實作。
- 【概念】給定一個陣列 A[ ] = {A1, A2, A3, A4, A5, A6, A7, A8, A9}
- 計算區間和 sum({A3, A4, A5, A6}) = sum({ A1, A2, A3, A4, A5, A6}) – sum({A1, A2})
- 只要對任意的 i，都能算出前綴和 sum({A1, …, Ai})，就可以求得任意區間和。
- 【複雜度】
- 時間複雜度：O(log(N))
- 空間複雜度：O(N)
- 【實作】update(x, d)：更新 BIT 的值 (第 x 項的值加上 d, delta)，下圖以A13 + d為例。
- 關鍵計算：x += x & (-x)
- BIT數組中的B[13], B[14], B[16] 都包含A13，因此必須一併更新。
void update(int x, int d){
// update prefix sum in BIT
while(x <= N){
b[x] += d;
x += x & (-x);
}
}
- 【實作】query(x)：利用BIT 計算前 x 項的和，下圖以 sum({A1, A2, …, A13})為例。
- 關鍵計算：x -= x & (-x)
- 答案為BIT數組中的 B[13] + B[12] + B[8]。
int query(int x){
// 以 BIT 計算和
int ret = 0;
while (x){
ret += b[x];
x -= x & (-x);
}
return ret;
}
【範例】ZeroJudge d794: 世界排名【題解】
【解題想法】數值離散化 + BIT
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
int N, M;
int b[100001]; //BIT
vector<ll> v, d;
int getID(ll x){
//離散化
return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
}
int query(int x){
// query prefix sum in BIT
int ret = 0;
while (x){
ret += b[x];
x -= x & (-x);
}
return ret;
}
void update(int x, int d){
// update prefix sum in BIT
while(x <= N){
b[x] += d;
x += x & (-x);
}
}
int main(){
while (cin >> N){
for (int i=1; i<=N; i++){
b[i] = 0; //clear BIT
}
v.clear();
for (int i=0; i<N; i++){
cin >> M;
v.push_back(M);
}
d = v;
sort(d.begin(), d.end());
// 去除重複的數字
// d.erase(unique(d.begin(), d.end()), d.end());
for (int i=1; i<=N; i++) {
int idx = getID(v[i-1]);
update(idx, 1);
cout << i - query(idx) + 1 << '\n';
}
}
return 0;
}