区间信息维护与查询【树状数组 】 - 原理2 多维树状数组

区间信息维护与查询【树状数组 】 - 原理2 多维树状数组

我们已经知道一维树状数组修改和查询的时间复杂度均为O (logn)，可以扩展为m 维树状数组，其时间复杂度为O (log ^m n )，对该算法只需加上一层循环即可。二维数组a [n ][n ]、树状数组c [][]的查询和修改方法如下。

【1】查询前缀和

二维数组的前缀和实际上是从数组左上角到当前位置(x , y )矩阵的区间和，在一维数组查询前缀和的代码中加上一层循环即可。

算法代码：

int sum(int x, int y){ //求左上角(1, 1) 到右下角(x , y) 矩阵区间和
	
	int s = 0;
	for(int i = x; i > 0 ; i -= lowbit(i)){
		
		for(int j = y ; j > 0 ; j -= lowbit(j)){
			s += c[i][j];
		}
	}
	return s;
}
1
2
3
4
5
6
7
8
9
10
11

【2】更新

若对a [x ][y ]进行修改（加上z ），则在一维数组更新的代码中加上一层循环即可。

算法代码：

void add(int x , int y , int z){ // a[x][y] 加上z
	for(int i = x ; i <= n; i += lowbit(i)){
		for(int j = y ; j <= n; j += lowbit(j)){
			c[i][j] += z;
		}
	}
}
1
2
3
4
5
6
7

【3】 查询区间和值。

对二维数组查询区间和，实际上是求从左上角(x 1 , y 1 )到右下角(x 2 , y 2 )子矩阵的区间和。先求出左上角(1,1)到右下角(x 2 , y 2 )的区间和sum(x 2 , y 2 )，然后减去(1, 1)到(-1, y 2 )的区间和sum(x 1 -1, y 2 )，再减去(1, 1)到(x 2 , y 1 -1)的区间和sum(x 2 , y 1 -1)，因为这两个矩阵的交叉区域多减了一次，所以再加回来，加上(1, 1)到(x 1 -1, y 1 -1)的区间和sum(x 1 -1, y 1 -1)。

算法代码：

int sum(int x1 ,int y1, int x2, int y2){ //求左上角 (x1, y1) 到右下角(x2 , y2) 子矩阵的区间和
	return sum(x2 , y2) - sum(x1 - 1 , y2) - sum(x2 , y1 - 1) + sum(x1 - 1 , y1 - 1);
}
1
2
3

④ 树状数组的局限性

树状数组主要用于查询前缀和、区间和及点更新，对点查询、区间修改效率较低。

前缀和查询： 求a [1]…a [i ]的前缀和，普通数组需要O (n )时间，树状数组需要O (logn )时间。

区间和查询： 求a [i ]…a [j ]的区间和，普通数组需要O (n )时间，树状数组需要O (logn )时间。

点更新： 修改a [i ]加上z ，普通数组需要O (1)时间，树状数组需要O (logn )时间。

点查询： 查找第i 个元素，普通数组需要 O (1)时间，树状数组需要O (logn )时间（求sum[i ]-sum[i -1]）。

区间修改： 若对一个区间a [i ]…a [j ]的所有元素都加上z ，则普通数组需要O (n )时间，树状数组不能有效操作，只能一个一个地修改和更新，需要O (n logn )时间。

减法规则： 当问题满足减法规则时，例如求区间和a [i ]…a [j]，则sum(i , j )=sum[j ]-sum[i -1]。当问题不满足减法规则时，例如求区间a [i ]…a [j ]的最大值，则不可以用a [1]…a [j ]的最大值减去a [1]…a [i -1]的最大值，此时可以用线段树解决。