P4514 上帝造题的七分钟
二维树状数组裸题。
定义二维差分数组：
\[d(i)(j)=a(i)(j)-a(i-1)(j)-a(i)(j-1)+a(i-1)(j-1)
\]
\]
如何维护\(1,1\)到\(i,j\)的二维前缀和？
\[sum(x)(y)=\sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{l=1}^jd(i)(j)\\
=\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*(x+1-i)*(y+1-i)\\
=(x+1)*(y+1)*\sum_{i=1}^x\sum_{j=1}^yd(i)(j)-(y+1)\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*i\\-(x+1)*\sum_{i=1}^x\sum_{j=1}^y*j+\sum_{i=1}^x\sum_{j=1}^y*d(i)(j)*i*j
\]
=\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*(x+1-i)*(y+1-i)\\
=(x+1)*(y+1)*\sum_{i=1}^x\sum_{j=1}^yd(i)(j)-(y+1)\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*i\\-(x+1)*\sum_{i=1}^x\sum_{j=1}^y*j+\sum_{i=1}^x\sum_{j=1}^y*d(i)(j)*i*j
\]
按照上述式子维护四个前缀和数组即可。
具体操作：
code:
void add(int posx,int posy,int k){
for(int i=posx;i<=n;i+=(i&-i)){
for(int j=posy;j<=m;j+=(j&-j)){
sum1[i][j]+=k;
sum2[i][j]+=k*posx;
sum3[i][j]+=k*posy;
sum4[i][j]+=k*posx*posy;
}
}
}
int query(int posx,int posy){
int re=0;
for(int i=posx;i>=1;i-=(i&-i)){
for(int j=posy;j>=1;j-=(j&-j)){
re+=((posx+1)*(posy+1))*sum1[i][j]-(posy+1)*sum2[i][j]-(posx+1)*sum3[i][j]+sum4[i][j];
}
}
return re;
}
void add_wx(int x1,int x2,int y1,int y2,int k){
add(x1,y1,k);
add(x1,y2+1,-k);
add(x2+1,y1,-k);
add(x2+1,y2+1,k);
}
int query_wx(int x1,int x2,int y1,int y2){
return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
}
针对本题：
code：
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
using namespace std;
const int wx=3017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
return sum*f;
}
int sum1[wx][wx];
int sum2[wx][wx];
int sum3[wx][wx];
int sum4[wx][wx];
int n,m;
char opt[4];
/*
d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
sum1[i][j]-->d[i][j]
sum2[i][j]-->d[i][j]*i
sum3[i][j]-->d[i][j]*j
sum4[i][j]-->d[i][j]*i*j
sum[x1][y1][x2][y2]=(x+1)*(y+1)*sum1[i][j]-(y+1)*sum2[i][j]-(x+1)*sum3[i][j]+sum4[i][j]。
*/
void add(int posx,int posy,int k){
for(int i=posx;i<=n;i+=(i&-i)){
for(int j=posy;j<=m;j+=(j&-j)){
sum1[i][j]+=k;
sum2[i][j]+=k*posx;
sum3[i][j]+=k*posy;
sum4[i][j]+=k*posx*posy;
}
}
}
int query(int posx,int posy){
int re=0;
for(int i=posx;i>=1;i-=(i&-i)){
for(int j=posy;j>=1;j-=(j&-j)){
re+=((posx+1)*(posy+1))*sum1[i][j]-(posy+1)*sum2[i][j]-(posx+1)*sum3[i][j]+sum4[i][j];
}
}
return re;
}
void add_wx(int x1,int x2,int y1,int y2,int k){
add(x1,y1,k);
add(x1,y2+1,-k);
add(x2+1,y1,-k);
add(x2+1,y2+1,k);
}
int query_wx(int x1,int x2,int y1,int y2){
return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
}
int main(){
scanf("%s");
n=read(); m=read();
while(scanf("%s",opt+1)!=EOF){
if(opt[1]=='L'){
int x,y,z,c,k;
x=read(); y=read(); z=read(); c=read(); k=read();
add_wx(x,z,y,c,k);
}
else{
int x,y,z,c;
x=read(); y=read(); z=read(); c=read();
printf("%d\n",query_wx(x,z,y,c));
}
}
return 0;
}