1013: 【模板】四分树（二维线段树 / 二维树状数组） 时间限制: 4 Sec 内存限制: 512 MB
提交: 4 解决: 2
[提交][状态][讨论版][命题人:stone41123][Edit] [TestData]
题目描述
给定一个n*m的矩阵，有q个操作，分为两种，分别为update和sum
对于每一个update，给出(x1,y1)为左上角坐标，(x2,y2)为右下角坐标，val为给这个区域加上val
对于每一个sum，给出(x1,y1)为左上角坐标，(x2,y2)为右下角坐标，输出区域的元素和
输入
第一行三个正整数，n,m,q
接下来n行，每行m个正整数，描述这个矩阵的初始值
接下来q行，每行描述一个操作，第一个数字为opt，当opt=1时为update，当opt=2时为sum
输出
对于每一个sum，输出其结果
样例输入
5 5 8
2 8 5 1 10
5 9 9 3 5
6 6 2 8 2
2 6 3 8 7
2 5 3 4 3
1 2 1 2 4 8
1 2 3 4 5 8
2 1 2 5 4
1 4 2 4 5 2
2 3 3 4 5
2 3 2 5 4
2 2 1 4 1
1 2 1 4 3 5
样例输出
152
84
83
21
提示
对于20%的数据，1<=n,m<=10，1<=q<=100
对于50%的数据，1<=n,m<=100，1<=q<=1000
对于70%的数据，1<=n,m<=500，1<=q<=20000
对于100%的数据，1<=n,m<=800，1<=q<=50000
保证答案不超过C++的long long，Pascal的int64
【四分树】随便搞了个板子题，然后尝试着写一下传说中的四分树，发现挺好写
就是莫名其妙四分树常数爆炸，开了4s才够，极限数据跑了3700ms左右
四分树就是用一个类似于线段树的东西来维护一个矩阵，就是每个点有四个儿子
然后每个儿子代表切分之后的一块区域，具体可以看我的代码
代码：
#include
#include
#include
#include
#include
#include
#define ll long long
#define lu rt<<2
#define ld rt<<2|1
#define ru rt<<2|2
#define rd rt<<2|3
using namespace std;
inline int read(){
int x=0;
char ch=' ';
int f=1;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=805,M=N*N*16;
int n,m,q;
ll sum[M],add[M],size[M],a[N][N];
inline void pushup(int rt){sum[rt]=sum[lu]+sum[ld]+sum[ru]+sum[rd];
}
inline void pushdown(int rt){
if(add[rt]){
add[lu]+=add[rt];
sum[lu]+=size[lu]*add[rt];
add[ld]+=add[rt];
sum[ld]+=size[ld]*add[rt];
add[ru]+=add[rt];
sum[ru]+=size[ru]*add[rt];
add[rd]+=add[rt];
sum[rd]+=size[rd]*add[rt];
add[rt]=0;
}
}
inline void build(int rt,int lx,int ly,int rx,int ry){
if(lx>rx||ly>ry)return;
size[rt]=(rx-lx+1)*(ry-ly+1);
if(lx==rx&&ly==ry){sum[rt]=a[lx][ly];
return;
}
int midx=(lx+rx)>>1,midy=(ly+ry)>>1;
build(lu,lx,ly,midx,midy);
build(ld,lx,midy+1,midx,ry);
build(ru,midx+1,ly,rx,midy);
build(rd,midx+1,midy+1,rx,ry);
pushup(rt);
}
int X1,Y1,X2,Y2;
ll val,ans;
inline void update(int rt,int lx,int ly,int rx,int ry){
if(lx>rx||ly>ry)return;
if(X1<=lx&&rx<=X2&&Y1<=ly&&ry<=Y2){add[rt]+=val;
sum[rt]+=val*size[rt];
return;
}
pushdown(rt);
int midx=(lx+rx)>>1,midy=(ly+ry)>>1;
if(X1<=midx&&Y1<=midy)update(lu,lx,ly,midx,midy);
if(X1<=midx&&midy+1<=Y2)update(ld,lx,midy+1,midx,ry);
if(midx+1<=X2&&Y1<=midy)update(ru,midx+1,ly,rx,midy);
if(midx+1<=X2&&midy+1<=Y2)update(rd,midx+1,midy+1,rx,ry);
pushup(rt);
}
inline void query(int rt,int lx,int ly,int rx,int ry){
if(lx>rx||ly>ry)return;
if(X1<=lx&&rx<=X2&&Y1<=ly&&ry<=Y2){ans+=sum[rt];
return;
}
pushdown(rt);
int midx=(lx+rx)>>1,midy=(ly+ry)>>1;
if(X1<=midx&&Y1<=midy)query(lu,lx,ly,midx,midy);
if(X1<=midx&&midy+1<=Y2)query(ld,lx,midy+1,midx,ry);
if(midx+1<=X2&&Y1<=midy)query(ru,midx+1,ly,rx,midy);
if(midx+1<=X2&&midy+1<=Y2)query(rd,midx+1,midy+1,rx,ry);
pushup(rt);
}
int main(){
n=read();
m=read();
q=read();
for(int i=1;
i<=n;
i++)for(int j=1;
j<=m;
j++)a[i][j]=read();
build(1,1,1,n,m);
while(q--){
int opt=read();
X1=read();
Y1=read();
X2=read();
Y2=read();
if(opt==1)val=read(),update(1,1,1,n,m);
else ans=0,query(1,1,1,n,m),printf("%lld\n",ans);
}
return 0;
} 
