在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。 一个玩家不时地会想知道某一个范围的鼹鼠总数。请你快速回答。
输入有若干行： 第一行，一个数n，表示鼹鼠的范围。 以后每一行开头都有一个数m，表示不同的操作： m=1，那么后面跟着3个数x,y,k，表示在点(x,y)处新出现了k只鼹鼠； m=2，那么后面跟着4个数x1,y1,x2,y2表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量； m=3，表示游戏结束，不能玩了。保证这个数会在输入的最后一行。 询问数不会超过10000，鼹鼠数不会超过maxlongint。
对于每个m=2，输出一行数，这行数只有一个数，即所询问的区域内鼹鼠的个数。
4 1 2 2 5 2 0 0 2 3 3
5
第一次用二维树状数组orz 犯了一个低级错误 modify（x.y）时，因为可以考虑原点，所以说当x==0或者y==0时，就会让modify函数陷入死循环== 然后我就T了很多次orz 该打 好了进入正题 这道题实际上运用了一个二维树状数组 至于改动的函数 int getsum(int x,int y) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j))sum+=c[i][j]; return sum; } void modify(int x,int y,int z) { int i,j; for(i=x;i<=n;i+=lowbit(i)) for(j=y;j<=n;j+=lowbit(j)) c[i][j]+=z; } 通过此道理，空间里面的坐标也可以处理了，通过二维数组可以推广到n维数组（当然要在题目要求的范围的） 回到题目，要求某个区域里面的sum，就用大的正方形减去两个长方形再加上多减的那个小矩形就可以了，和平面直角坐标系中求面积是同样的道理，所以说最后要求的就是下面这坨东西 getsum(a,b)+getsum(c+1,d+1)-getsum(a,d+1)-getsum(c+1,b)；
附上代码：
#include<iostream> using namespace std; long long C[1030][1030],n,m,x,y,z,a,b,c,d; int lowbit(int x){return x&-x;} void modify(int x,int y,int z) { int i,j; for(i=x;i<=n;i+=lowbit(i)) for(j=y;j<=n;j+=lowbit(j)) C[i][j]+=z; } int getsum(int x,int y) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j))sum+=C[i][j]; return sum; } int main() { cin>>n; while(1) { cin>>m; if(m==3)break; if(m==1) { cin>>x>>y>>z; modify(x+1,y+1,z); } if(m==2) { cin>>a>>b>>c>>d; cout<<getsum(a,b)+getsum(c+1,d+1)-getsum(a,d+1)-getsum(c+1,b)<<endl; } } }