数格子

有一个S*S的方格，行和列都是从0到S-1。

有四种操作：

操作	参数	含义
0	S	初始化表格，大小为S*S，所有单元格的值均为0。（此操作只出现一次且一定是第一条操作）
1	X Y A	将（X，Y ）单元格的值增加A
2	L B R T	询问矩形区域(x,y)内的值的和并输出答案，其中x,y满足 L<= x <= R, B <= y <= T
3	无	结束，此操作只出现一次且一定是最后一条

范围限制：

方格大小	S*S	1 <= S <= 1024
任意时刻单元格的值V	V	0 <= V <= 32767
每次增加的值A	A	-23768 <= A <= 23767
输入的操作总数	M	3 <= M <= 60002
所有单元格值之和	T	T <= 2³⁰

Input

本题只有一组测试数据。

第一行为操作0。

最后一行为操作3。

中间操作数不多于60000。

Output

输入输出格式请参考Description和Sample。

Sample Output

0 4

1 1 2 3

2 0 0 2 2

1 1 1 2

1 1 2 -1

2 1 1 2 3

Hint

裸的二维树状数组。

所求区域和 sum = sum(R, T) – sum(R,B-1) – sum(L-1,T) + sum(L-1,B-1)

注意S及坐标应从1开始，所以应对输入坐标做 +1处理。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define S 1030
int c[S][S];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void Updata(int x,int y,int val)
{
    for(int i=x; i<=n; i+=lowbit(i))
    {
        for(int j=y; j<=n; j+=lowbit(j))
        {
            c[i][j]+=val;
        }
    }
}
int Getsum(int x,int y)
{
    int sum=0;
    for(int i=x; i>0; i-=lowbit(i))
    {
        for(int j=y; j>0; j-=lowbit(j))
        {
            sum+=c[i][j];
        }
    }
    return sum;
}
int main()
{
    int tt, cmd, x, y, val;
    int x1, y1, x2, y2;
    freopen("B.in","r",stdin);
    freopen("X.out","w",stdout);
    scanf("%d%d",&tt,&n);
    memset(c,0,sizeof(c));
    while(scanf("%d",&cmd) && cmd<3)
    {
        if(cmd==1)
        {
            scanf("%d%d%d",&x,&y,&val);
            x++;
            y++;
            Updata(x,y,val);
        }
        else if(cmd==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++, y1++, x2++, y2++;
            int ans=Getsum(x2,y2)-Getsum(x2,y1-1)-Getsum(x1-1,y2)+Getsum(x1-1,y1-1);
            printf("%d ",ans);
        }
    }
    return 0;
}