二维树状数组 单点更新区间查询 模板

从零开始借鉴http://www.2cto.com/kf/201307/227488.html

#include<stdio.h>

#include<string.h>

#define N 1100

int c[N][N],visit[N][N],n;

int number(int x) {

return x&-x;

}

void insert(int x,int y,int z) {

int i,j;

for(i=x;i<=N;i+=number(i))//到最大的范围N，而不是n.

for(j=y;j<=N;j+=number(j))

c[i][j]+=z;

}

int sum(int x,int y) {

int i,j,su=0;

for(i=x;i>0;i-=number(i))

for(j=y;j>0;j-=number(j))

         su+=c[i][j];

return su;

}

int main() {

int i,j,a,b,x1,x2,y1,y2;

char s[3];

while(scanf("%d",&n)!=EOF) {

memset(visit,0,sizeof(visit));

memset(c,0,sizeof(c));

while(n--) {

scanf("%s",s);

if(s[0]=='B') {

scanf("%d%d",&a,&b);

a++;b++;

if(visit[a][b])

continue;

visit[a][b]=1;

insert(a,b,1);

}

if(s[0]=='D') {

scanf("%d%d",&a,&b);

a++;b++;

if(visit[a][b]==0)

continue;

visit[a][b]=0;

insert(a,b,-1);

}

if(s[0]=='Q') {

scanf("%d%d%d%d",&x1,&x2,&y1,&y2);

x1++;x2++;y1++;y2++;

if(x1>x2) {i=x1;x1=x2;x2=i;}

if(y1>y2) {i=y1;y1=y2;y2=i;}

j=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);//用x2,y2范围内的减去x2,y1-1和x1-1,y2范围内的加上多减了一个x1-1,y1-1。

printf("%d\n",j);

}

}

}

return 0;

}