二维线段树

树套树可见

https://www.cnblogs.com/mimiorz/p/10295452.html

或

https://blog.zcmimi.top/posts/xian-duan-shu-tao-xian-duan-shu

这张图是对二维线段树的解释（也就是棵四叉树）

它其实本质上和线段树是一样的，只要比较了解普通的线段树就可以学会二维的。

二维线段树的每个节点都是矩阵的一个部分，有四个孩子

假设一个节点是这样一个矩阵：（如下图）

四个孩子就是四个颜色部分的矩阵。

但要注意：最后可能会分剩下这样两种要做特殊处理的矩阵（如下图）：

这时候就要特判，使访问过程不能超出矩阵范围，我的做法是建一个bool的数组，将其余两个节点做标记，一遇到标记就返回这个节点的父亲。

接下来就上代码啦：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<map>
 6 #include<cmath>
 7 #define ll long long
 8 #define max(x,y) ((x)>(y)?(x):(y))
 9 #define min(x,y) ((x)<(y)?(x):(y))
10 #define fur(i,x,y) for(i=x;i<=y;i++)
11 #define fdr(i,x,y) for(i=x;i>=y;i--)
12 #define Fur(i,x,y) for(ll i=x;i<=y;i++)
13 #define Fdr(x,y) for(ll i=x;i>=y;i--)
14 #define in2(x,y) in(x);in(y)
15 #define in3(x,y,z) in2(x,y);in(z)
16 #define in4(a,b,c,d) in2(a,b);in2(c,d)
17 #define clr(x,y) memset(x,y,sizeof(x))
18 #define cpy(x,y) memcpy(x,y,sizeof(x))
19 using namespace std;
20 /*---------------------------------------*/
21 namespace fib{char b[300000]= {},*f=b;}
22 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
23 inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
24 namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}
25 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
26 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
27 struct foce{~foce(){pob;fflush(stdout);}} _foce;
28 namespace ib{char b[100];}
29 inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}
30 inline void outn(ll x){out(x);pc('
');}
31 inline ll jdz(ll x){return x>0?x:-x;}
32 /*------------------------------------------------------------------------------------------------*/
33 
34 /*------------------------------------------------------------------------------------------------*/
35 #define N 2334
36 #define c1 (rt*4-2)
37 #define c2 (rt*4-1)
38 #define c3 (rt*4)
39 #define c4 (rt*4+1)
40 #define z1 x1,y1,mx,my
41 #define z2 x1,my+1,mx,y2
42 #define z3 mx+1,y1,x2,my
43 #define z4 mx+1,my+1,x2,y2
44 #define Z ll mx=(x1+x2)>>1,my=(y1+y2)>>1
45 #define U ll x1,ll y1,ll x2,ll y2,ll rt
46 #define pu s[rt]=s[c1]+s[c2]+s[c3]+s[c4]
47 ll s[N*N*4],laz[N*N*4],a[N][N],n,m,q,g[N*N*4];
48 bool b[N*N*4];
49 inline ll gs(ll x1,ll y1,ll x2,ll y2){return (jdz(x1-x2)+1)*(jdz(y1-y2)+1);}
50 inline void pd(ll rt,ll n1,ll n2,ll n3,ll n4){
51     if(laz[rt]){ll &t=laz[rt];
52         s[c1]+=n1*t;s[c2]+=n2*t;s[c3]+=n3*t;s[c4]+=n4*t;
53         laz[c1]+=t;laz[c2]+=t;laz[c3]+=t;laz[c4]+=t;
54         t=0;
55     }
56 }
57 inline void build(U){
58     g[rt]=gs(x1,y1,x2,y2);
59     if(x1==x2&&y1==y2){s[rt]=a[x1][y1];return;}
60     Z;
61     build(z1,c1);if(y1!=y2)build(z2,c2);else b[c2]=1;
62     if(x1!=x2)build(z3,c3);else b[c3]=1;if(x1!=x2&&y1!=y2)build(z4,c4);else b[c4]=1;
63     pu;
64 }
65 inline void upd(ll X1,ll Y1,ll X2,ll Y2,ll v,U){
66     if(b[rt])return;
67     if(X1<=x1&&Y1<=y1&&x2<=X2&&y2<=Y2){s[rt]+=gs(x1,y1,x2,y2)*v;laz[rt]+=v;return;}
68     Z;pd(rt,g[c1],g[c2],g[c3],g[c4]);
69     if(X1<=mx&&Y1<=my)upd(X1,Y1,X2,Y2,v,z1,c1);
70     if(X1<=mx&&Y2>my)upd(X1,Y1,X2,Y2,v,z2,c2);
71     if(X2>mx&&Y1<=my)upd(X1,Y1,X2,Y2,v,z3,c3);
72     if(X2>mx&&Y2>my)upd(X1,Y1,X2,Y2,v,z4,c4);
73     pu;
74 }
75 inline ll qh(ll X1,ll Y1,ll X2,ll Y2,U){
76     if(b[rt])return 0;
77     if(X1<=x1&&Y1<=y1&&x2<=X2&&y2<=Y2)return s[rt];
78     Z,ans=0;pd(rt,g[c1],g[c2],g[c3],g[c4]);
79     if(X1<=mx&&Y1<=my)ans+=qh(X1,Y1,X2,Y2,z1,c1);
80     if(X1<=mx&&Y2>my)ans+=qh(X1,Y1,X2,Y2,z2,c2);
81     if(X2>mx&&Y1<=my)ans+=qh(X1,Y1,X2,Y2,z3,c3);
82     if(X2>mx&&Y2>my)ans+=qh(X1,Y1,X2,Y2,z4,c4);
83     return ans;
84 }
85 int main(){
86     in3(n,m,q);
87     Fur(i,1,n)Fur(j,1,m)in(a[i][j]);
88     build(1,1,n,m,1);
89     ll p,x1,y1,x2,y2,v;
90     while(q--){
91         in(p);in4(x1,y1,x2,y2);
92         if(p==1)outn(qh(x1,y1,x2,y2,1,1,n,m,1));
93         else{in(v);upd(x1,y1,x2,y2,v,1,1,n,m,1);}
94     }
95 }