【POJ No. 1195】 矩形区域查询 Mobile phones

北大 OJ 题目地址

【题意】

移动电话的基站区域分为多个正方形单元，形成S ×S 矩阵，行和列的编号为0～S -1，每个单元都包含一个基站。一个单元内活动手机的数量可能发生变化，因为手机从一个单元移动到另一个单元，或手机开机、关机。

编写程序，改变某个单元的活动手机数量，并查询给定矩形区域中当前活动手机的总数量。

【输入输出】

输入：

输入和输出均为整数。每个输入都占一行，包含一个指令和多个参数。所有值始终在以下数据范围内。

若A 为负，则可以假设它不会将值减小到零以下。

• 表大小：1×1≤S ×S ≤1024×1024。
• 单元值：0≤V ≤32767。
• 更新量：-32768≤A ≤32767。
• 输入中的指令数：3≤U ≤60002。
• 整个表中的最大电话数：M =2^30 。

输出：

对指令2，单行输出矩形区域中当前活动手机的总数量。

【样例】

【思路分析】

这道题包括单点更新与矩形区间和查询，是非常简单的二维树状数组问题。

【算法设计】

直接采用二维树状数组进行点更新和矩阵区间和查询即可。

注意：本题坐标从0开始，树状数组下标必须从1开始，所以对输入下标做加1处理。

【算法实现】

#include
#include
#define maxn 1050
#define lowbit(x) (x)&(-x)int c[maxn][maxn],n;void add(int x,int y,int z)//单点更新 
{for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))c[i][j]+=z;
}int sum(int x,int y)//区间和：左上角(1,1)到右下角(x,y)矩阵区间和 
{int s=0;for(int i=x;i>0;i-=lowbit(i))for(int j=y;j>0;j-=lowbit(j))s+=c[i][j];return s;
}int sum(int x1,int y1,int x2,int y2)//求左上角(x1,y1)到右下角(x2,y2)子矩阵区间和 
{return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
}int main()
{int opt,x,y,a,l,b,r,t;while(scanf("%d",&opt)!=EOF){if(opt==3) break;if(opt==0){scanf("%d",&n);memset(c,0,sizeof(c));}else if(opt==1){scanf("%d%d%d",&x,&y,&a);++x;++y;add(x,y,a);}else{scanf("%d%d%d%d",&l,&b,&r,&t);++l,++b,++r,++t;printf("%d\n",sum(l,b,r,t));}}return 0;
}