hdu2642二维树状数组单点更新

时间:2022-07-15 10:20:03

碰到这种题一定要注意坐标是不是有序的,也要注意坐标是不是有0的,有的话需要+1处理

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int bit[maxn][maxn],flag[maxn][maxn];
char op[];
void add(int x,int y,int num){
for(int i=x;i<=;i+=i&-i)
for(int j=y;j<=;j+=j&-j)
bit[i][j]+=num;
}
int query(int x,int y){
int res=;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
res+=bit[i][j];
return res;
}
int main(){
int m,x1,y1,x2,y2;
while(scanf("%d",&m)==){
memset(bit,,sizeof bit);
memset(flag,,sizeof flag);
while(m--){
scanf("%s",op);
if(op[]=='B'){
scanf("%d%d",&x1,&y1);
x1++,y1++;
if(flag[x1][y1]) continue;
add(x1,y1,);
flag[x1][y1]=;
}
else if(op[]=='D'){
scanf("%d%d",&x1,&y1);
x1++,y1++;
if(flag[x1][y1]==) continue;
add(x1,y1,-);
flag[x1][y1]=;
}
else {
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
x1++,y1++,x2++,y2++;
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
printf("%d\n",query(x2,y2)-query(x1-,y2)-query(x2,y1-)+query(x1-,y1-));
}
}
}
return ;
}