【範例】二維BIT (樹狀數組)
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d847
- bit[x][y]：相對於 ( x , y )，有多少個點 ( a , b ) 在它的左下方 a < x , b < y。
- 每讀入一組 ( xi , yi ) ，即更新bit，表示增加一點到所有受影響的區間（前綴和即為比該點小的點的個數），xi <= x <= 1000, yi <= y <= 1000。
- query( x, y )：有多少個點 ( a , b ) 滿足 a < x , b < y，或 a <= x – 1 , b <= y – 1。
- (Line-34)：注意，本題有多組測試資料。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1005;
int n, bit[maxn][maxn], qx, qy, a[10005][2];
void update(int x, int y){
while (x < maxn){
int ty = y;
while (ty < maxn){
bit[x][ty]++;
ty += ty & (-ty);
}
x += x & (-x);
}
}
int query(int x, int y){
int ret = 0;
while (x){
int ty = y;
while (ty){
ret += bit[x][ty];
ty -= ty & (-ty);
}
x -= x & (-x);
}
return ret;
}
int main() {
while (cin >> n){
memset(bit, 0, sizeof(bit));
for (int i = 0; i < n; i++){
cin >> a[i][0] >> a[i][1];
update(a[i][0], a[i][1]);
}
for (int i = 0; i < n; i++){
cout << query(a[i][0]-1, a[i][1]-1) << "\n";
}
}
return 0;
}