前言
这几题都是二维树状数组的模板，不得不说树状数组真是个好东西，既好写速度又快常数还小。但是二维上的处理讲真搞到了我。也使我对差分和前缀和这两个好用的工具有了更深的理解
所有题目都是基于 n\times m 的零矩阵上进行的操作。
LOJ133 单点修改，区间查询
题目链接：https://loj.ac/problem/133
不难发现，我们需要处理的树状数组变成二维的信息之后，在每次的加和查询的操作时，都只需要多考虑一维就可以了，即循环多加一层，需要注意的是这时候就不能直接将传入的 x 和 y 进行操作了，因为每一层关于 y 的内循环都要从 y 的初始值开始考虑。
这里需要注意二维前缀和的技巧：如果需要求 (a,b) 到 (c,d) 间的矩阵的和的话，假设 s_{i,j} 为 (1,1) 到 (i,j) 的前缀和，则答案为
s_{c,d}-s_{a-1,d}-s_{c,b-1}+s_{a-1,b-1}
具体的证明咕咕咕了，哪天有时间再写，其实就相当于把多加了减掉，多减了的加回来而已。
具体见下：
#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;
const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];
void add(int x,int y,int d)
{
for(int xx=x;xx<=n;xx+=lowbit(xx))
for(int yy=y;yy<=m;yy+=lowbit(yy))
f[xx][yy]+=d;//和一维的很像，但只是加了一维而已
return;
}
ll sum(int x,int y)//查询操作也一样
{
ll ans=0;
for(;x>0;x-=lowbit(x))
for(int yy=y;yy>0;yy-=lowbit(yy))
ans+=f[x][yy];
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
int t,a,b,c,d,k;
while(scanf("%d",&t)!=EOF)
{
if(t==1)
{
scanf("%d %d %d",&a,&b,&k);
add(a,b,k);
}
else
{
scanf("%d %d %d %d",&a,&b,&c,&d);
ll ans=sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1);
printf("%lld\n",ans);
}
}
return 0;
}
LOJ134 区间修改，单点查询
题目链接：https://loj.ac/problem/134
涉及区间修改的时候就需要用到差分了，二维的差分和一维的差分其实本质上没有任何的区别，具体的操作和二维前缀和的有些相似，也是咕咕咕改天写。
单点查询就只需利用 BIT 求出差分的前缀和就可以了，具体见下：
#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;
const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];
void add(int x,int y,int d)
{
for(int xx=x;xx<=n;xx+=lowbit(xx))
for(int yy=y;yy<=m;yy+=lowbit(yy))
f[xx][yy]+=d;
return;
}
ll sum(int x,int y)
{
ll ans=0;
for(;x>0;x-=lowbit(x))
for(int yy=y;yy>0;yy-=lowbit(yy))
ans+=f[x][yy];
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
int t,a,b,c,d,k;
while(scanf("%d",&t)!=EOF)
{
if(t==2)
{
scanf("%d %d",&a,&b);
printf("%lld\n",sum(a,b));
}
else
{
scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
add(a,b,k),add(a,d+1,-k),add(c+1,b,-k),add(c+1,d+1,k);//这里是差分的处理
}
}
return 0;
}
LOJ135 区间修改，区间查询
题目链接：https://loj.ac/problem/135
到这里就比较麻烦了，二维线段树我不会打，怎么办呢？只能考虑用树状数组来同时照顾前缀和和差分了。
不妨令 a_{i,j}=\displaystyle\sum_{x=1}^i\sum_{y=1}^jd_{x,y}，即 d 为二维差分数组，而我们又由前缀和的定义知道 s_{k,l}=\displaystyle\sum_{x=1}^k\sum_{y=1}^ja_{i,j}，因此类比一维的情况，考虑用含有差分的式子来表示前缀和，数学推导过程如下，由于我很笨，所以有可能存在小瑕疵，而且过程很不简洁：
\begin{aligned}
&\sum_{k=1}^x\sum_{l=1}^ya_{k,l}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^k\sum_{j=1}^l d_{i,j}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^kd_{i,l}\times(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(x-k+1)(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy-ky+y-xl+kl-l+x-k+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy+x+y+1-l-k+kl-xl-ky)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times[xy+x+y+1-l(1+x)-k(1+y)+kl]\
=&(x+1)(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}-(x+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l-(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k+\sum_{k=1}^x\sum_{l=1}^yd_{k,l}kl
\end{aligned}
其中 a_{k,l}=\displaystyle\sum_{i=1}^k\sum_{j=1}^l d_{i,j}
所以需要维护四个 BIT，分别是 \displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}，\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l，\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k，\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}lk
每次修改的时候四个 BIT 要联动修改，当推出了公式之后，剩下的事情就很简单了，写出代码实现即可，我不会告诉你我抄错了我自己推的式子导致 WA 两次。注意不要漏了要乘的东西就可以了，代码如下：
#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;
const int maxn=2058;
ll f1[maxn][maxn],f2[maxn][maxn],f3[maxn][maxn],f4[maxn][maxn];
int n,m;
void add(ll x,ll y,ll d)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
f1[i][j]+=d,
f2[i][j]+=x*d,
f3[i][j]+=y*d,
f4[i][j]+=x*y*d;
return;
}
ll sum(ll x,ll y)
{
ll ans1=0,ans2=0,ans3=0,ans4=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans1+=f1[i][j],
ans2+=f2[i][j],
ans3+=f3[i][j],
ans4+=f4[i][j];
return ans1*(x+1)*(y+1)-ans2*(y+1)-ans3*(x+1)+ans4;
}
int main()
{
scanf("%d %d",&n,&m);
ll t,a,b,c,d,x;
while(scanf("%lld %lld %lld %lld %lld",&t,&a,&b,&c,&d)!=EOF)
{
if(t==1)
{
scanf("%lld",&x);
add(a,b,x),add(a,d+1,-x),add(c+1,b,-x),add(c+1,d+1,x);
}
else
printf("%lld\n",sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1));
}
return 0;
}
大概就是这么多，先睡了，明天再继续肝。