PKU1195 Mobile phones - 二维树状数组

本文主要是介绍PKU1195 Mobile phones - 二维树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

在一个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;
}
 