学步园

http://poj.org/problem?id=1195

题意：有一个s*s的方格，有两种操作，给某个方格a[x][y] 加上一个数add 和 询问某一个子矩阵内所有数字的和。

思路：二维树状数组的模板。。要注意的是题目中的下标从0开始而树状数组的下标从1开始，所以下标均向右移一位。

#include <stdio.h>
#include <string.h>

const int maxn = 1030;
int Lowbit(int x)
{
	return x&(-x);
}

int c[maxn][maxn];
int n;

//给a[i][j]节点加上add;
void update(int i, int j, int add)
{
	while(i <= n)
	{
		int tmp = j;
		while(tmp <= n)
		{
			c[i][tmp] += add;
			tmp += Lowbit(tmp);
		}
		i += Lowbit(i);
	}
}

//a[1][1]~a[i][j]的和（原数组）
int sum(int i, int j)
{
	int s = 0;
	while(i > 0)
	{
		int tmp = j;
		while(tmp > 0)
		{
			s += c[i][tmp];
			tmp -= Lowbit(tmp);
		}
		i -= Lowbit(i);
	}
	return s;
}

int main()
{
	int f;
	int x,y,add;
	int l,r,b,t;
	memset(c,0,sizeof(c));
	while(1)
	{
		scanf("%d",&f);
		if(f == 0)
			scanf("%d",&n);
		else if(f == 1)
		{
			scanf("%d %d %d",&x,&y,&add);
			update(x+1,y+1,add);
		}
		else if(f == 2)
		{
			scanf("%d %d %d %d",&l,&b,&r,&t);
			l++;//均向后移一位，相对位置不变
			r++;
			b++;
			t++;
			int ans = sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1);
			printf("%d\n",ans);
		}
		else if(f == 3)
			break;
	}
	return 0;
}