题目描述：
在一个N*N的区域内，可以在某个点增加或减少A，并动态询问一个矩形区域内的数值之和。（N<=1024）
分析：
典型的二维树状数组的应用。
以前有几篇论文讨论了如何要用二维线段树来做，相当麻烦。不过二维树状数组则十分简单。
不过树状数组的应用范围很窄，如果修改题目为“可以给某个矩形区域每个点增加或减少A，并动态询问某个点的数值”那么树状数组就不行了，而线段树可以使用。
- /*
- PKU1195 Mobile phones
- */
- #include <stdio.h>
- #include <memory.h>
- #define clr(a) memset(a,0,sizeof(a))
- #define N 1030
- int c[N][N];
- int n;
- int lowbit(int x){
- return x&(-x);
- }
- void Update(int x,int y,int t){
- int i,j;
- i=x;
- while(i<=n){
- j=y;
- while(j<=n){
- c[i][j]+=t;
- j+=lowbit(j);
- }
- i+=lowbit(i);
- }
- }
- int Query(int x,int y){
- int i,j,s=0;
- i=x;
- while(i>0){
- j=y;
- while(j>0){
- s+=c[i][j];
- j-=lowbit(j);
- }
- i-=lowbit(i);
- }
- return s;
- }
- int main()
- {
- int i,j,k;
- int x,y,xt,yt,t;
- scanf("%*d%d",&n);
- while(scanf("%d",&k)!=EOF && k!=3){
- if(k==1){ //Update
- scanf("%d%d%d",&x,&y,&t);
- x++;y++;
- Update(x,y,t);
- }
- if(k==2){ //Query
- scanf("%d%d%d%d",&x,&y,&xt,&yt);
- x++;y++;xt++;yt++;
- t=Query(xt,yt)-Query(x-1,yt)-Query(xt,y-1)+Query(x-1,y-1);
- printf("%d/n",t);
- }
- }
- return 0;
- }