二维树状数组
-
什么是二维树状数组
- 二维树状数组是在一维树状数组的基础上拓展而来的一个由数字构成的大矩阵，能进行两种操作对矩阵里的某个数加上一个整数（可正可负）或查询某个子矩阵里所有数字的和，要求对每次查询，输出结果。
-
二维树状数组
-
一维树状数组 (c_i=a_{i-lowbit(i)+1}+a_{i-lowbit(i)+2}+...+a_i)
-
二维树状数组：
[egin{aligned} c_{i,j}&=a_{i-lowbit(i)+1,j-lowbit(j)+1}+a_{i-lowbit(i)+1,j-lowbit(j)+2}+...+a_{i-lowbit(i)+1,j}\ &=a_{i-lowbit(i)+2,j-lowbit(j)+1},+...+a_{i-lowbit(i)+2,j-lowbit(j)+2}+...+a_{i-lowbit(i)+2,j}\ &=...\ &=a_{i,j-lowbit(j)+1}+a_{i,j-lowbit(j)+2+...+a_{i,j}} end{aligned} ] -
显然二维树状数组 (c_{i,j}) 维护的是以 ((i,j)) 的右下角的宽为 (lowbit(i)) ，高为 (lowbit(j)) 矩阵内元素之和。
-
二维数组的更新和查询跟一维就是多了一维，维护一个矩阵。
-
-
单点修改，区间查询
- 求左下角坐标 ((a,b)) 到右上角坐标 ((c,d)) 矩阵的和。假设 (sum[i][j]) 表示左下角 ((1,1)) 到右上角 ((i,j)) 矩阵元素之和，则所求矩阵元素和为：(ans=sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1]) 。
#include <bits/stdc++.h> const int maxn=4096+5; typedef long long ll; ll c[maxn][maxn]; int n,m; int lowbit(int x){return x & -x;} void modify(int x,int y,int z){//点(x,y)增加z for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) c[i][j]+=z; } ll getsum(int x,int y){//求左上角为(1,1)右下角为(x,y) 的矩阵和 ll tot=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) tot+=c[i][j]; return tot; } void Solve(){ scanf("%d%d",&n,&m); int ch; while(~scanf("%d",&ch)){ if(ch==1){ int x,y,k; scanf("%d%d%d",&x,&y,&k); modify(x,y,k); } else{ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); printf("%lld ",getsum(c,d)-getsum(c,b-1)-getsum(a-1,d)+getsum(a-1,b-1)); } } } int main(){ Solve(); return 0; } -
区间修改单点查询
-
一维树状数组区间修改单点查询是维护了差分数组，这样差分数组前缀和等于原数组对应位置的元素。
-
二维数组如何进行差分，使二维前缀和为原矩阵位置元素值呢？
-
令 (d[i][j]) 表示差分数组，(a[i][j]) 为原矩阵元素值，则：
-
(d[i][j]=a[i][j]-(a[i-1][j]+a[i][j-1]-a[i-1][j-1]))
-
例如下面矩阵
#原数组 1 4 8 6 7 2 3 9 5 #差分数组 1 3 4 5 -2 -9 -3 5 1- 我们对二维差分数组求前缀和，正好是原矩阵元素值。
-
当我们想要将一个矩阵加上 (x) 时，怎么做呢？如下面是给最中间的(3 imes 3) 矩阵加上 (x) 时，差分数组的变化：
# 更新时分别对矩阵四个角做如下更新(左上角为原点) # 左上角坐标(x1,y1),右下角坐标(x2,y2) # 更新时在(x1,y1)处 +x,相当于对矩阵 (x1,y1)到(n,m)都加上了x # 在(x1,y2+1)处-x,消除对矩阵(x1,y2+1)到(n,m)多加的x # 在(x2+1,y1)处-x,消除对矩阵(x2+1,y1)到(n,m)多加的x # 在(x2+1,y2+1)处+x,(x2+1,y2+1)到(n,m)被上面三个操作都就算了一遍，被加了一次x，减去两次x,所以再加一次x消除影响。 0 0 0 0 0 0 +x 0 0 -x 0 0 0 0 0 0 0 0 0 0 0 -x 0 0 +x # 单点getsum求值时，矩阵结果如下： 0 0 0 0 0 0 x x x 0 0 x x x 0 0 x x x 0 0 0 0 0 0 -
(Code)
#include <bits/stdc++.h> const int maxn=4096+5; typedef long long ll; ll c[maxn][maxn]; int n,m; int lowbit(int x){return x & -x;} void modify(int x,int y,int z){//点(x,y)增加z for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)){ c[i][j]+=z; } } ll getsum(int x,int y){ ll tot=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) tot+=c[i][j]; return tot; } void Solve(){ scanf("%d%d",&n,&m); int ch; while(~scanf("%d",&ch)){ if(ch==1){ int x1,x2,y1,y2,k;//左上角(a,b),右下角(c,d)，增加k scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k); modify(x1,y1,k); modify(x2+1,y2+1,k); modify(x2+1,y1,-k); modify(x1,y2+1,-k); } else{ int x,y; scanf("%d%d",&x,&y); printf("%lld ",getsum(x,y)); } } } int main(){ Solve(); return 0; }
-
-
区间修改、区间查询
-
跟一维树状数组类似，(sum[i][j])：二维前缀和；(a[i][j])：矩阵元素的值；(d[i][j])：矩阵差分数组。
-
显然有：
[egin{aligned}sum[x][y]&=sum_{i_1=1}^xsum_{j_1=1}^y a[i_1][j_1]\&=sum_{i_1=1}^xsum_{j_1=1}^ysum_{i_2=1}^{i_1}sum_{j_2=1}^{j_1} d[i_2][j_2]end{aligned} ] -
用上面的式子要想求出二维前缀和，需要 (O(n^4)) 的时间效率，这太暴力，需要化简。
-
类比一维数组，在我们求 (sum[x][y]) 时：
差分数组 出现次数 (d[1][1]) (x*y) (d[1][2]) (x*(y-1)) …… …… (d[1][y]) $ x*1 $ $d[2][1] $ ((x-1)*y) …… …… (d[x][1]) (1*y) …… …… (d[x][y]) (1*1) - 所以 (d[i][j]) 在二维前缀和 $sum[x][y] $ 中出现了：((x-i+1)*(y-j+1)) 次。
-
把上式展开可以得到：
[egin{aligned} sum[x][y]&=(x+1-i)*(y+1-j)*sum_{i=1}^xsum_{j=1}^y d[i][j]\ &=((x+1)*(y+1)-(x+1)*j-(y+1)*i+i*j)*sum_{i=1}^xsum_{j=1}^y d[i][j]\ &=(x+1)*(y+1)*sum_{i=1}^xsum_{j=1}^y d[i][j]-(y+1)*sum_{i=1}^xsum_{j=1}^y d[i][j]*i-(x+1)*sum_{i=1}^xsum_{j=1}^y d[i][j]*j+sum_{i=1}^xsum_{j=1}^y d[i][j]*i*j\ end{aligned} ] -
所以我们只需开四个树状数组，分别维护：(d[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*j) 。
-
(Code)
#include <bits/stdc++.h> const int maxn=2048+5; typedef long long ll; ll c1[maxn][maxn],c2[maxn][maxn],c3[maxn][maxn],c4[maxn][maxn]; int n,m; int lowbit(int x){return x & -x;} void modify(ll x,ll y,ll z){//点(x,y)增加z for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)){ c1[i][j]+=z; c2[i][j]+=x*z; c3[i][j]+=y*z; c4[i][j]+=x*y*z; } } ll getsum(ll x,ll y){ ll tot=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) tot+=(x+1)*(y+1)*c1[i][j]-(y+1)*c2[i][j]-(x+1)*c3[i][j]+c4[i][j]; return tot; } void Solve(){ scanf("%d%d",&n,&m); int ch; while(~scanf("%d",&ch)){ if(ch==1){ int x1,x2,y1,y2;//左上角(a,b),右下角(c,d)，增加k ll k; scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&k); modify(x1,y1,k); modify(x2+1,y2+1,k); modify(x2+1,y1,-k); modify(x1,y2+1,-k); } else{ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%lld ",getsum(x2,y2)+getsum(x1-1,y1-1)-getsum(x2,y1-1)-getsum(x1-1,y2)); } } } int main(){ Solve(); return 0; }
-