1 首先从一维的开始，考虑最基础的单点修改，区间查询。树状数组模板1：这个是最基础的，就是定义的应用。
2再考虑区间修改，单点查询。树状数组模板2。
我们可以想到，在对一段区间(;[l,r];)进行修改时，可以将(;[1,r];)加上(;k),将(;[1,l-1];)减去(;k;)。但这样修改，对于单点查询来说，似乎不是那么的方便，我们可能需要求出(;[1,x];)和(;[1,x-1];)的前缀和，再做个差。好像...有点麻烦。
那么有什么更好的方法呢？——考虑差分。
我们定义(;d_i=a_i-a_{i-1},;a_0=0;)。那么每次修改，就只需要将(;d_l;)和(;d_{r+1};)进行修改，而单点查询即为(;sumlimits_{i=1}^xd_i)。直接进行前缀和查询即可。
3还有的就是区间修改，区间求和了。线段树模板1。
我们跟着上面区间修改，单点查询的思路来，还是考虑差分。
修改的话，如同上面一样，只对差分数组(;d_{l-1};)和(;d_r;)进行修改，但有些许变动。
我们来看一个式子：
这个式子前一半表示的是区间(;[1,r];)的和，后一半是区间(;[1,l-1];)的和，二者做差即为所求的区间(;[l,r];)的和。
尝试对其化简。
我们先只考虑前一半，即(;sumlimits_{i=1}^rsumlimits_{j=1}^id_j)。
发现(;d_1;)出现了(;r;)次，(;d_2;)出现了(;r-1;)次(;ldots) (d_x;)出现了(;r-x+1;)次。至此，我们发现式子可以变为：
展开可得：
最终我们只需开两个树状数组来维护(;d_i;)和(;d_i imes i;)即可。
修改：
il void add(int x,ll val)
{
for(int i=x;i<=n;i+=lowbit(i))
c1[i]+=val,c2[i]+=x*val;
}
il void real_add(int l,int r,int val)
{
add(l,val);
add(r+1,-val);
}
查询：
il ll ask(int x)
{
ll ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=c1[i]*(x+1)-c2[i];
return ans;
}
il ll real_ask(int l,int r)
{
return ask(r)-ask(l-1);
}
4接下来考虑单点修改，区间查询。二维树状数组模板。
我们只需将一维扩展到二维，代码只需进行一定的修改即可：
修改：
inline void add(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
a[i][j]+=val;
}
查询：
inline int ask(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
asn+=a[i][j];
return ans;
}
5最后是区间修改，区间查询。上帝造题的七分钟。
回想一下，我们是怎么进行一维的区间修改的——差分。差分数组(;sumlimits_{i=1}^nd_i=a_i;)。再想一下差分数组是如何求出来的。
我们来看两个式子：
应该能发现什么吧——差分数组的计算有点像前缀和计算的逆运算。所以，我们可以仿照二维数组的前缀和公式来推出二维数组的差分公式。
在回想一下，我们在进行一维数组的差分修改时是如何修改的——再将其扩展到二维。
当我们要修改一个二维区间 (;(x_1,y_1) (x_2,y_2);) 所组成的矩形时，只需修改(;(x_1,y_1) (x_1,y_2+1) (x_2+1,y_1) (x_2+1,y_2+1);)四个点。那么，如何修改呢？
我们来看一个式子：
我们发现，(;d_{11};) 出现了(;x imes y;)次，(;d_{12};)出现了 (;x imes {(y-1)};)次(;ldots) (;d_{pq};)出现了(;{(x-p+1)} imes {(y-q+1)};)次。
我们将式子展开，可得到
再次展开
那么，我们就只需开四个树状数组来分别维护(d_{ij}quad d_{ij} imes iquad d{ij} imes jquad d{ij} imes i imes j)即可。
区间查询就是(;sum_{{x_2}{y_2}}-sum_{{x_2}{y_1-1}}-sum_{{x_1-1}{y_2}}+sum_{{x_1-1}{y_1-1}})
完整代码：
//2020.11.4
//二维树状数组，区间修改，区间查询
#include<bits/stdc++.h>
using namespace std;
const int maxn=2050;
#define NEKO puts("NEKO")
#define il inline
#define vocaloid(v) (v>='0'&&v<='9')
il int read()
{
int x=0,flag=1;char v=getchar();
while(!vocaloid(v)) {if(v=='-') flag=-1;v=getchar();}
while(vocaloid(v)) {x=(x<<1)+(x<<3)+v-'0';v=getchar();}
return x*flag;
}
il int lowbit(int x) {return x&(-x);}
int n,m,c1[maxn][maxn],c2[maxn][maxn],c3[maxn][maxn],c4[maxn][maxn];
char ch;int X1,X2,Y1,Y2,val;
il void add(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
{
c1[i][j]+=val;
c2[i][j]+=val*x;
c3[i][j]+=val*y;
c4[i][j]+=val*x*y;
}
}
il void real_add(int X1,int Y1,int X2,int Y2,int val)
{
add(X1,Y1,val);
add(X1,Y2+1,-val);
add(X2+1,Y1,-val);
add(X2+1,Y2+1,val);
}
il int ask(int x,int y)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans+=(x+1)*(y+1)*c1[i][j]-(y+1)*c2[i][j]-(x+1)*c3[i][j]+c4[i][j];
return ans;
}
il int real_ask(int X1,int Y1,int X2,int Y2)
{
return ask(X2,Y2)-ask(X2,Y1-1)-ask(X1-1,Y2)+ask(X1-1,Y1-1);
}
int main()
{
cin>>ch;n=read(),m=read();
while(cin>>ch)
{
if(ch=='L')
{
X1=read(),Y1=read(),X2=read(),Y2=read(),val=read();
real_add(X1,Y1,X2,Y2,val);
}
if(ch=='k')
{
X1=read(),Y1=read(),X2=read(),Y2=read();
printf("%d
",real_ask(X1,Y1,X2,Y2));
}
}
return 0;
}
(PS) 部分内容参考自以下几篇博客：
十分感谢他们的博客对我学习此内容的帮助。