二维树状数组的应用
#include<iostream> using namespace std; #define maxn 1030 int c[maxn][maxn]; int low(int k) { return k&(-k); } void update(int x,int y,int n,int a) { for(int i=x;i<=n;i+=low(i)) for(int j=y;j<=n;j+=low(j)) c[i][j]+=a; return ; } int query(int x,int y) { int i,j,sum=0; for(i=x;i>0;i-=low(i)) for(j=y;j>0;j-=low(j)) sum+=c[i][j]; return sum; } int main() { int n,x1,y1,x2,y2,s,a,sum; memset(c,0,sizeof(c)); while(1) { scanf("%d",&n); if(n==0) scanf("%d",&s); else if(n==1) { scanf("%d%d%d",&x1,&y1,&a); x1++,y1++; update(x1,y1,s,a); } else if(n==2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++,y1++,x2++,y2++; sum=query(x2,y2)-query(x1-1,y2) -query(x2,y1-1)+query(x1-1,y1-1); printf("%d/n",sum); } else break; } return 0; }
