POJ 1195 Mobile phones(二维树状数组)

题目链接：http://poj.org/problem?id=1195

题意是有四种操作。

当n==0时：输入一个m表示初始化矩阵(m*m且值都为0)。

当n==1时：输入x,y,z，表示(x,y)点加上z。

当n==2时：输入x,y,z,d，输出坐标(x,y)到坐标(z,d)的总和。

当n==3时：结束输入。

二维树状数组的入门模板题了，其实二维和一维的差不多，一维的理解了，二维的看着代码想一下就差不多了。

AC代码：

1#include <iostreaM>
2#include <cstdio>
3#include <cstring>
4#define maxn 2005
5using namespace std;
6int pre[maxn][maxn];
7int n,m,x,z,y,d;
8
9int lowbit(int x){return x & (-x);}
10
11void Add(int x,int y,int z){
12	for(int i=x;i<=m;i+=lowbit(i)){
13		for(int j=y;j<=m;j+=lowbit(j)){
14			pre[i][j] += z;
15		}
16	}
17}
18
19int Query(int x,int y){
20	int sum = 0;
21	for(int i=x;i>=1;i-=lowbit(i)){
22		for(int j=y;j>=1;j-=lowbit(j)){
23			sum += pre[i][j];
24		}
25	}
26	return sum;
27}
28
29int main()
30{
31	while(~scanf("%d",&n)){
32		if(n == 3)break;
33		if(n == 0){
34			scanf("%d",&m);
35			for(int i=1;i<=m;i++){
36				for(int j=1;j<=m;j++){
37					pre[i][j] = 0;
38				}
39			}
40		}
41		if(n == 1){
42			scanf("%d%d%d",&x,&y,&z);
43			x++;y++;
44			Add(x,y,z);
45		}
46		if(n == 2){
47			scanf("%d%d%d%d",&x,&y,&z,&d);
48			x++;y++;z++;d++;
49			printf("%d\n",Query(z, d)-Query(x-1, d)-Query(z, y-1)+Query(x-1, y-1));
50		}
51	}
52	return 0;
53}

本文同步分享在 博客“Ch_zaqdt”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。