\(\color{purple}\text{Ⅰ.二维树状数组}\)

\(\color{orange}\text{例一：P3372 【模板】线段树 1}\)

$\color{green}\text{2023.1.10 14:32} $
回忆一下树状数组的区间修改与查询操作，后面有用。

维护差分数组 \(\text{de[i]}\)。
则:

\(\sum_{i=1}^{n}a[i]\)
\(=(de[1])+(de[1]+de[2])+(de[1]+de[2]+de[3])\dots +(de[1]+de[2]+\dots+de[n])\)
\(=de[1]\times n+de[2]\times (n-1)+\dots+de[n]\times 1\)
\(=\sum_{i=1}^{n}de[i]\times (n+1)-\sum_{i=1}^nde[i]\times i\)

\(\color{purple}\text{例二：P4514 上帝造题的七分钟}\)

\(\color{green}\text{2023.1.10 17:58}\)
二维树状数组。

同上面 \(\color{pink}Case37\) 一维的一样来推式子。

先推怎么差分，这个画个图推，想办法让其差分前缀和等于原数。然后得到下图：

所以差分的方法为：
\((a,b)\to+1\)
\((c+1,d+1)\to+1\)
\((a,d+1)\to-1\)
\((c+1,b)\to-1\)

可以修改了，对吧。

然后怎么查询：

\(\sum_{i=1}^{x}\sum_{j=1}^{y}a[i][j]\)
\(=\)
\(de[1][1]+(de[1][1]+de[1][2])+(de[1][1]+de[1][2]+de[1][3])+\dots+\)
\((de[1][1]+de[2][1])+\{(de[1][1]+de[1][2])+(de[2][1]+de[2][2])\}+\dots +\)
\((de[1][1]+de[2][1]+de[3][1])+\dots +\)
\(\dots\)
(发现对于一个 \(de[i][j]\) 从它到右下角的数都涉及它)
\(=\sum_{i=1}^{x}\sum_{j=1}^{y}de[i][j]\times(x-i+1)\times(y-i+1)\)
(然后我推了半天，发现画图能很好地推出来)

\(=\sum_{i=1}^{x}\sum_{j=1}^{y}de[i][j]\times x \times y-de[i][j]\times(i-1)\times y-de[i][j]\times(j-1)\times x+de[i][j]\times (i-1)\times (j-1)\)

上面的值都能维护了啊。
那么二维树状数组就结束了。

\(\color{lightblue}\text{Code}\)

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=3010;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,m,de[N][N],dei[N][N],dej[N][N],deij[N][N];
void ude(int x,int y,int k){
	for(int i=x;i<=n;i+=i&(-i))
		for(int j=y;j<=m;j+=j&(-j))
			de[i][j]+=k;
	return;
}
void udei(int x,int y,int k){
	for(int i=x;i<=n;i+=i&(-i))
		for(int j=y;j<=m;j+=j&(-j))
			dei[i][j]+=k;
	return;
}
void udej(int x,int y,int k){
	for(int i=x;i<=n;i+=i&(-i))
		for(int j=y;j<=m;j+=j&(-j))
			dej[i][j]+=k;
	return;
}
void udeij(int x,int y,int k){
	for(int i=x;i<=n;i+=i&(-i))
		for(int j=y;j<=m;j+=j&(-j))
			deij[i][j]+=k;
	return;
}
int query(int it[][N],int x,int y){
	int res=0;
	for(int i=x;i>0;i-=i&(-i))
		for(int j=y;j>0;j-=j&(-j))
			res+=it[i][j];
	return res;
}
int getsum(int x,int y){
	return query(de,x,y)*x*y-query(dei,x,y)*y-query(dej,x,y)*x+query(deij,x,y);
}
char Startrunning,opt;
signed main(){cin>>Startrunning;
	n=1+read(),m=1+read();
	while(scanf("%s",&opt)!=EOF){
		if(opt=='L'){
			int a=1+read(),b=1+read(),c=1+read(),d=1+read(),k=read();
			ude(a,b,k);
			ude(c+1,d+1,k);
			ude(a,d+1,-k);
			ude(c+1,b,-k);
			
			udei(a,b,k*(a-1));
			udei(c+1,d+1,k*c);
			udei(a,d+1,-k*(a-1));
			udei(c+1,b,-k*c);
			
			udej(a,b,k*(b-1));
			udej(c+1,d+1,k*d);
			udej(a,d+1,-k*d);
			udej(c+1,b,-k*(b-1));
			
			udeij(a,b,k*(a-1)*(b-1));
			udeij(c+1,d+1,k*c*d);
			udeij(a,d+1,-k*(a-1)*d);
			udeij(c+1,b,-k*(b-1)*c);
		}
		else{
			int a=1+read(),b=1+read(),c=1+read(),d=1+read();
			printf("%d\n",getsum(c,d)-getsum(a-1,d)-getsum(c,b-1)+getsum(a-1,b-1));
		}
	}
	return 0;
}