二维树状数组
因为要区间修改区间和,所以得要四个,差不多就是做类似于前缀和的前缀和那样
题解:http://hi.baidu.com/strongoier/item/13f22104f6b4c50d6c904852
AC-Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2052;
int n,m;
int B1[MAXN][MAXN],B2[MAXN][MAXN],B3[MAXN][MAXN],B4[MAXN][MAXN];
inline int LowBit(int x)
{
return x&(-x);
}
void add(int (*s)[MAXN],int x,int y,int d)
{
for (int i=x;i<=n;i+=LowBit(i))
for (int j=y;j<=m;j+=LowBit(j))
s[i][j]+=d;
}
int sum(int (*s)[MAXN],int x,int y)
{
int ret=0;
for (int i=x;i>0;i-=LowBit(i))
for (int j=y;j>0;j-=LowBit(j))
ret+=s[i][j];
return ret;
}
void ADD(int x,int y,int d)
{
if (!x||!y)
return;
add(B1,x,y,x*y*d);
add(B2,x,1,x*d);add(B2,x,y,-x*d);
add(B3,1,y,y*d);add(B3,x,y,-y*d);
add(B4,1,1,d);add(B4,x,y,d);add(B4,x,1,-d);add(B4,1,y,-d);
}
int QUERY(int x,int y)
{
return x&&y?(sum(B1,x,y)+sum(B2,x,y)*y+sum(B3,x,y)*x+sum(B4,x,y)*x*y):0;
}
int main()
{
char op[20];
int x1,y1,x2,y2,d;
scanf("%s%d%d",op,&n,&m);
while (scanf("%s%d%d%d%d",op,&x1,&y1,&x2,&y2)!=EOF)
{
if (op[0]=='L')
{
scanf("%d",&d);
ADD(x2,y2,d);ADD(x1-1,y1-1,d);
ADD(x2,y1-1,-d);ADD(x1-1,y2,-d);
}else
{
printf("%d\n",QUERY(x2,y2)-QUERY(x2,y1-1)-QUERY(x1-1,y2)+QUERY(x1-1,y1-1));
}
}
return 0;
}