题意是在二维平面上在一些位置上进行数据的增删改查操作，使用树状数组（了解树状数组点这里）
原来的树状数组在求区间和时是 sum( x, y ) = getsum( y ) - getsum( x - 1 )，
在这道题中是 sum( x1, y1, x2, y2 ) = getsum( x2,y2 ) - getsum( x1-1, y2 ) - getsum( x2, y1-1 ) + getsum( x1-1, y1-1 )
如图所示：
注意所给位置是从 0 开始算的，用树状数组时要从 1 开始算，也就是说要在所有的坐标上加 1 。还要注意书架上开始时每个位置都有一本书。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int x,y,xx,yy,n,t,k,cnt,num,shelf[][];
char ch;
int lowbit(int x)
{
return x & (-x);
}
int aa(int x,int y)
{
int sum = ;
for(int i = x; i > ; i -= lowbit(i))
for(int j = y; j > ; j -= lowbit(j))
sum += shelf[i][j];
return sum;
}
void update(int x,int y,int val)
{
for(int i = x; i <= ; i+=lowbit(i))
for(int j = y; j <= ; j+=lowbit(j))
shelf[i][j] += val;
}
void init()
{
memset(shelf,,sizeof(shelf));
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
update(i,j,);
}
void s(int x,int y,int xx,int yy)
{
if(x>xx)
{
k = xx;
xx = x;
x = k;
}
if(y>yy)
{
k = yy;
yy = y;
y = k;
}
printf("%d\n",aa(xx+,yy+)-aa(x,yy+)-aa(xx+,y)+aa(x,y));
} int get_s(int x,int y)
{
return aa(x,y) - aa(x-,y) - aa(x,y-) + aa(x-,y-);
}
void d(int x,int y,int n)
{
k = get_s(x+,y+);
n = n>k?k:n;
update(x+,y+,-n);
}
void m(int x,int y,int xx,int yy,int n)
{
k = get_s(x+,y+);
n = n>k?k:n;
update(x+,y+,-n);
update(xx+,yy+,n);
}
int main()
{
scanf("%d",&t);
for(cnt = ; cnt <= t; ++cnt)
{
scanf("%d",&num);
printf("Case %d:\n",cnt);
init();
while(num--)
{
scanf("%c",&ch);
if(ch=='S')
{
scanf("%d%d%d%d",&x,&y,&xx,&yy);
s(x,y,xx,yy);
}
else if(ch=='A')
{
scanf("%d%d%d",&x,&y,&n);
update(x+,y+,n);
}
else if(ch=='D')
{
scanf("%d%d%d",&x,&y,&n);
d(x,y,n);
}
else if(ch=='M')
{
scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&n);
m(x,y,xx,yy,n);
}
else num++;
}
}
return ;
}