【HOJ1640】Mobile Phone-二维树状数组

题目大意：一个大小为S*S的方阵，有两种操作：1.将坐标为（x,y）的元素增加a。2.询问矩形区域（l,b）-（r,t）内所有元素之和。对于每个询问，给出正确的答案。

做法：基本的二维树状数组的题目，其他操作就是加一维就行了，不是很难理解。需要注意的是询问操作：设sum(x,y)为矩形区域（0,0）-（x,y）内所有元素之和，要求出矩形区域（l,b）-（r,t）内所有元素之和，可以得出结果为：sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1)，这里要注意，由于矩形区域（0,0）-（l-1,b-1）内的元素被减了两次，所以要把它们加回来。理解之后就没有什么难度了。

以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int s,op;
long c[1050][1050]={0};

int lowbit(int i)
{
  return i&(-i);
}

void add(int x,int y,int a)
{
  for(int i=x;i<=s;i+=lowbit(i))
    for(int j=y;j<=s;j+=lowbit(j))
	  c[i][j]+=a;
}

long sum(int x,int y)
{
  long sm=0;
  if (!x||!y) return 0;
  for(int i=x;i>0;i-=lowbit(i))
    for(int j=y;j>0;j-=lowbit(j))
	  sm+=c[i][j];
  return sm;
}

long query(int l,int b,int r,int t)
{
  return sum(r,t)-sum(r,b-1)-sum(l-1,t)+sum(l-1,b-1);
}

int main()
{
  while(scanf("%d",&op)!=EOF)
  {
    if (op==0)
	{
	  memset(c,0,sizeof(c));
	  scanf("%d",&s);
	}
	if (op==1)
	{
	  int x,y,a;
	  scanf("%d %d %d",&x,&y,&a);
	  add(x+1,y+1,a);
	}
	if (op==2)
	{
	  int l,b,r,t;
	  scanf("%d %d %d %d",&l,&b,&r,&t);
	  printf("%ld
",query(l+1,b+1,r+1,t+1));
	}
  }
  
  return 0;
}