二维树状数组

前置知识：树状数组学习

二维树状数组简介

二维树状数组用于处理二维数组中的查询和修改。和一维树状数组一样，二维树状数组代码短，常数和空间小，时间复杂度小，十分方便好用。

设原数组上的点为$a[i][j]$，二维树状数组上的点为$s[i][j]$，则

$s[x][y]=\sum _{i=tx}^x\sum _{j=ty}^{y}a[i][j]$

其中$tx=x-2^m+1$，$ty=y-2^n+1$
$m$表示$x$的二进制中末尾连续的0的个数，$n$表示$y$的二进制中末尾连续的0的个数。

二维树状数组的操作

单点修改

和一维树状数组类似，修改$a[i][j]$，要将所有含有$a[i][j]$的$s[i][j]$都修改。

code

void add(int x,int y,long long v){
	for(int i=x;i<=n;i+=lb(i)){
		for(int j=y;j<=m;j+=lb(j)){
			tr[i][j]+=v;
		}
	}
}
1
2
3
4
5
6
7

时间复杂度为$O({\log }^{2}n)$

区间查询

求$a$数组的二维前缀和，和一维树状数组的求法类似。

code

long long find(int x,int y){
	long long re=0;
	for(int i=x;i;i-=lb(i)){
		for(int j=y;j;j-=lb(j)){
			re+=tr[i][j];
		}
	}
	return re;
}
1
2
3
4
5
6
7
8
9

若要求$\sum _{i=a}^c\sum _{j=b}^{d}a[i][j]$，则答案为$find(c,d)-find(c-1,b)-find(a-1,d)+find(a-1,b-1)$。可以画图理解。

时间复杂度为$O({\log }^{2}n)$

例题

单点修改+区间查询模板的代码就是上面两个代码拼接起来，这里不再赘述。下面给一道有难度的题。

洛谷 P4514 上帝造题的七分钟

这道题涉及到区间查询和区间修改。

和一维树状数组一样，设$d$数组为$a$数组的差分，即$d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

则$a[x][y]=\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]$

对于区间修改，设将$(a,b)$和$(c,d)$为顶点的矩形内每个数都增加$v$，则$d[c][d]+=v,d[c][b-1]-=v,d[a-1][d]-=v,d[a-1][b-1]+=v$即可，这样就变成了单点修改。

对于区间查询：
$sum[x][y]=\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]$
$=\sum _{i=1}^x\sum _{j=1}^y\sum _{i^{\prime }=1}^i\sum _{j^{\prime }=1}^{j}d[i^{\prime }][j^{\prime }]$
$=\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]\ast (x-i+1)\ast (y-j+1)$
$=(x+1)(y+1)\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]-(y+1)\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]\ast i-(x+1)\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]\ast j+\sum _{i=1}^x\sum _{j=1}^{y}d[i][j]\ast i\ast j$

所以，我们需要维护$d[i][j],d[i][j]\ast i,d[i][j]\ast j,d[i][j]\ast i\ast j$的前缀和，即可求出$a[i][j]$的和。

code

#include
using namespace std;
int n,m,tr[2505][2505][4];
char ch;
int lb(int i){
	return i&(-i);
}
void add(int x,int y,long long v){
	for(int i=x;i<=n;i+=lb(i)){
		for(int j=y;j<=m;j+=lb(j)){
			tr[i][j][0]+=v;
			tr[i][j][1]+=v*x;
			tr[i][j][2]+=v*y;
			tr[i][j][3]+=v*x*y;
		}
	}
}
long long find(int x,int y,int z){
	long long re=0;
	for(int i=x;i;i-=lb(i)){
		for(int j=y;j;j-=lb(j)){
			re+=tr[i][j][z];
		}
	}
	return re;
}
long long sum(int x,int y){
	return (x+1)*(y+1)*find(x,y,0)-(y+1)*find(x,y,1)-(x+1)*find(x,y,2)+find(x,y,3);
}
int main()
{
	int a,b,c,d;
	long long v;
	scanf("%c%d%d",&ch,&n,&m);
	while(scanf("%c",&ch)!=EOF){
		if(ch!='L'&&ch!='k') continue;
		if(ch=='L'){
			scanf("%d%d%d%d%d",&a,&b,&c,&d,&v);
			add(a,b,v);
			add(c+1,b,-v);
			add(a,d+1,-v);
			add(c+1,d+1,v);
		}
		else{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			printf("%d\n",sum(c,d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1));
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50