题解 P4514 【上帝造题的七分钟】
kuansoudafahao
2018-05-11 23:23:57
# 二维树状数组
**二维树状数组**是一个十分~~胡扯~~玄妙的算法。它和一维树状数组有着相同的地方，那就是**lowbit**运算。在一维树状数组中，我们用tree[x]记录右端点为x，长度为lowbit(x)的区间的区间和。我们同样可以类似地定义tree[x][y]为右下端点为(x,y),高为lowbit(x),宽为lowbit(y)的区间的区间和。
## 那么我们如何对其进行**区间修改**呢？
我们回忆一下我们是如何对一维树状数组进行区间修改的。我们对其进行差分操作，是为了使得到的差分数组前缀和就等于对应位置元素的值。那么我们可以运用类比思想，设计一个二维的差分呢？
#### 什么是差分数组呢？
对于一个数组$A[ ]$，其差分数组$D[i]=A[i]-A[i-1] (i>0)$且$D[0]=A[0]$
令$SumD[i]=D[0]+D[1]+D[2]+…+D[i]$ （SumD[ ]是差分数组D[ ]的前缀和）
则$SumD[i]=A[0]+A[1]-A[0]+A[2]-A[1]+A[3]-A[2]+…+A[i]-A[i-1]=A[i] $
即$A[i]$的差分数组是$D[i]$， 而$D[i]$的前缀和是$A[i]$
#### 回归正题
我们来看一下二维的前缀和。
$$sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]$$
查询左上角点（x1,y1），右下角点(x2,y2)的区间和则是：$$sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]$$
那么我们可以使差分数组$d[i][j]$等于$a[i][j]$和$a[i-1][j]+a[i][j-1]-a[i-1][j-1]$的差。
如下矩阵:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
当我们想给中间那个2*3的矩阵加上x时，差分数组的变化应该是：
0 0 0 0 0
0 +x 0 0 -x
0 0 0 0 0
0 -x 0 0 +x
至于为什么要这样，我们要等到区间查询时就会发现。
## **区间查询**
根据差分数组的定义，我们不难发现，对于点(x,y)，它的二维前缀和就是:
$$\sum_{i=1}^x\sum_{j=1}^y\sum_{h=1}^i\sum_{k=1}^j d[h][k]$$
但我们类比一下一维树状数组的区间求和，我们亦可以统计每个$d[h][k]$出现的次数，我们就可以发现$d[1][1]$出现了$(x\times y)$次，$d[1][2]$出现了$x\times(y-1)$次……$d[h][k]$出现了$(x-h+1)\times (y-k+1)$次。
则原式整理得：
$$\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times (x-i+1)\times (y-j+1)$$
分解得：
$$\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times [(xy-xj+x)+(-yi+ij-i)+(y-j+1)]$$
最后得：
$$\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times (xy+x+y+1)-d[i][j]\times i(y+1)-d[i][j]\times j(x+1)+d[i][j]\times i\times j$$
根据我们最后分解出来的公式，我们需要维护四个数组$d[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*j$，从而实现区间查询。
## 例题
[LuoguP4514 上帝造题的七分钟](https://www.luogu.org/problemnew/show/P4514)
非常适合我们的二维树状数组裸题。因为这题~~听说~~开二维线段树会爆空间，所以我们要使用二维树状数组。而且这题要开o2优化，不然过不了。~~惨痛的经历。~~原理我们已经讲得很清楚了，直接上代码。
```c++
// luogu-judger-enable-o2
#include <cstdio>
int n,m,num,x1,y1,x2,y2;
char c[3];
struct BIT
{
int tree[2050][2050];
int lowbit(int x) {return x&-x;}
void add(int x,int y,int num)
{
for(int i=x; i<=n; i+=lowbit(i))
for(int j=y; j<=m; j+=lowbit(j))
tree[i][j]+=num;
}
int query(int x,int y)
{
int res=0;
for(int i=x; i>=1; i-=lowbit(i))
for(int j=y; j>=1; j-=lowbit(j))
res+=tree[i][j];
return res;
}
}A,Ai,Aj,Aij;
int read()
{
int sign=1,res=0;
char c;
while((c=getchar())<48||c>57)
if(c=='-')
sign=-1;
if(sign)
res=c-48;
while((c=getchar())>=48&&c<=57)
res=res*10+c-48;
return res*sign;
}
int Ans(int x,int y)
{
return A.query(x,y)*(x*y+x+y+1)-
Ai.query(x,y)*(y+1)-
Aj.query(x,y)*(x+1)+
Aij.query(x,y);
}
void Add(int x,int y,int num)
{
A.add(x,y,num);
Ai.add(x,y,num*x);
Aj.add(x,y,num*y);
Aij.add(x,y,num*x*y);
}
int main()
{
scanf("X %d %d",&n,&m);
while(~scanf("%s",&c))
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(c[0]=='L')
{
scanf("%d",&num);
Add(x1,y1,num);
Add(x1,y2+1,-num);
Add(x2+1,y1,-num);
Add(x2+1,y2+1,num);
}else
{
printf("%d\n",Ans(x2,y2)-Ans(x1-1,y2)-Ans(x2,y1-1)+Ans(x1-1,y1-1));
}
}
return 0;
}
```
[参考地址](https://www.cnblogs.com/RabbitHu/p/BIT.html)