Poj 1195 Mobile phones(2 Dツリー配列ベース)

1294 ワード

http://poj.org/problem?id=1195
題意:s*sの四角形があり、ある四角形a[x][y]に1つの数addを加え、あるサブマトリクス内のすべての数字の和を尋ねる2つの操作がある.
考え方:2 Dツリー配列のテンプレート.なお,タイトルの下付き文字は0から,樹状配列の下付き文字は1からであるため,下付き文字はいずれも右に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
",ans); } else if(f == 3) break; } return 0; }