树状数组初探

古城微笑少年丶 2022-05-30 03:22 175阅读 0赞

## 前言 ##

在前一篇文章：[线段树初探][Link 1] 中我们看了一下线段树的基本思想并且知道了线段树擅长于解决区间问题。其实对于某些区间问题，我们不仅可以用线段树解决，还可以用树状数组解决。那么可能有小伙伴要问了，那既然线段树和树状数组都可以解决某些区间问题，那么我就一直用线段树就好了啊，为什么还要学树状数组呢？对于这个问题，我这里能给的答案是：对于两者都能解决的区间问题，两者所用的时间复杂度都是O(logn)，树状数组所用的内存空间比线段树更小，还有一个点是：实现树状数组的代码会比线段树的代码更少也更简单。下面来看一下树状数组的基本思想：

## 基本概念 ##

我们还是从一个题目说起：  
假设现在有 n 个数，编号为 1 ~ n（注意这里不是 0 ~ n-1，我们文末会讨论这个问题）。现在，每一次会给你一个区间 \[a, b\] （1 <= a <= b <= n），要求给出这 n 个数中编号在区间 \[a, b\] 中的数字的和。

对于这个问题，最简单也是最直观的做法就是先开一个长度为 n+1 的数组，这里我们命名为数组 A，之后对于每次查询，用循环求出数组 A 中下标在区间 \[a, b\] 范围内的元素值的和。这样的话每次查询的时间复杂度为 O(n)，如果有 m 次查询，那么总的时间复杂度为 O(m\*n)。下面我们用树状数组来优化这个时间复杂：

我们再开一个长度也为 n+1 的数组 C，这个 C 数组其实就是我们的树状数组。于是，数组 C 中也存在下标为 1~n 的总共 n 个元素。我们将数组 C 中的十进制下标转换为二进制，那么数组 C 中下标 1 ~ 10 对应的二进制为：

1 -----> 1  
2 -----> 10  
3 -----> 11  
4 -----> 100  
5 -----> 101  
6 -----> 110  
7 -----> 111  
8 -----> 1000  
9 -----> 1001  
10 -----> 1010

**我们设：C\[x\] = A\[x\] + A\[x - 1\] + A\[x - 2\] + …… + A\[x - k + 1\]**  
A 为我们开的长度为 n+1 用于储存 n 个数字的数组，C 为我们开的长度为 n+1 的另一个数组，x 为当前的数组下标，那么最后是 k：\*\*在这里，假设 i 为下标 x 对应的二进制数最右边的 0 的个数，那么 k = 2^i。\*\*可能这样说还是有点抽象，我们举个例子：当 x 为 8 时，其对应的二进制数为 1000，那么最右边的 0 的个数为 3 ，即 k = 2^3 = 8。  
于是我们有：  
**C\[8\] = A\[8\] + A\[7\] + A\[6\] + A\[5\] + A\[4\] + A\[3\] + A\[2\] + A\[1\]。**  
**当 x = 7 时，k = 2^0 = 1，于是 C\[7\] = A\[7\]。**  
**当 x = 6 时，k = 2^1 = 2，于是 C\[6\] = A\[6\] + A\[5\]**  
**当 x = 4 时，k = 2^2 = 4，于是 C\[4\] = A\[4\] + A\[3\] + A\[2\] + A\[1\]**

**结合上面的推导，我们可以推出：C\[8\] = A\[8\] + C\[7\] + C\[6\] + C\[4\]**  
**之后对于 x = 3 、x = 2，我们还可以推出：C\[3\] = A\[3\] 和 C\[2\] = A\[2\] + A\[1\]**  
**于是：C\[4\] = A\[4\] + C\[3\] + C\[2\]**

这个过程用这张图来表示再合适不过了：  
![这里写图片描述][70]  
图片出自：[https://www.cnblogs.com/GeniusYang/p/5756975.html][https_www.cnblogs.com_GeniusYang_p_5756975.html]

我们可以发现：当 x 为奇数时，C\[x\] = A\[x\]。

\*\*那么现在，如果我们需要求出数组 A 中区间 \[1, 8\] 元素的和，我们直接返回 C\[8\] 就可以了！因为此时 C\[8\] = A\[1\] + A\[2\] + …… + A\[8\]。\*\*对于区间 \[1, 8\] 如此，那么对于其它的区间，我们也可以这么做吗？比如将区间改成 \[1, 7\]，而此时 C\[7\] = A\[7\]（7 为奇数），显然，我们还需要加上 A\[1\] + A\[2\] + A\[3\] + A\[4\] + A\[5\] + A\[6\] 的值才是答案。再仔细看看图和我们之前的推导，我们会发现： **A\[1\] + A\[2\] + A\[3\] + A\[4\] = C\[4\]，A\[5\] + A\[6\] = C\[6\]。于是 A 数组中元素下标在区间 \[1, 7\] 内的元素和为：C\[7\] + C\[6\] + C\[4\]**

那么我们再思考一下：数字 7 和数字 6 和数字 4 之间有什么联系吗？  
回到上面的二进制，我们知道：7 的二进制为 111，6 的二进制为 110，4 的二进制为 100。  
**我们还是设 i 为 C 数组下标对应的二进制数的最右边的 0 的个数，设 k = 2^i。**  
对于 7 来说，它的 i 值为 0，因此它的 k = 2^0 = 1。  
对于 6 来说，它的 i 值为 1，因此它的 k = 2^1 = 2。  
对于 4 来说，它的 i 值为 2，因此它的 k = 2^2 = 4。

\*\*我们发现：7 - 1 = 6，6 - 2 = 4 \*\*  
**所以，我们只需要不断求出当前 C 数组下标 x 的 k 值，我们就能求出 A 数组中元素下标在区间 \[1, x\] 内的元素和。**  
于是，我们现在需要一个算法，用来对于每一个 C 数组的下标 x （x > 0），能够求出其对应的 k。这里直接给出一个算法，即为大名鼎鼎的 `lowbit`：

int lowbit(int x) {
        
    	return x & (-x);
    }

我们来尝试证明一下：我们知道计算机内部用补码表示数据，**而 `-x` 的补码即为 `x` 的补码按位取反后末位数 + 1**，这样做其实就相当于**将 x 最右边的 1 的左边所有位的值按位取反。我们来举个例子：假设当前 `x` 为 4，二进制为：`00000000000000000000000000000100`，则 `-x` 的补码为：`11111111111111111111111111111100`，为什么会有这个结论呢？因为我们强调了是x 最右边的 1**，我们暂且把 x 二进制表示中最右边的 1 所在的位设为第 y 位，也就是说在第 y 位的右边全是 0 (即最右边的 1)，取反之后第 y 位右边变成了全是 1，而第 y 位值本身取反后为 0，此时在末位 + 1 会从右向左产生进位。最后又会把第 y 位的值变为 1，而其右边因为进位变为 0，但是其左边却不会受影响，因为进位在第 y 为就结束了（第 y 位值取反时由 1 变为 0）。所以整个过程即为将第 y 位左边所有位的值按位取反，将第 y 位右边所有位的值设为 0。这也是负数补码的特点所在。此时 `x &(-x)` 的结果就很好理解了。因为 `-x` 的值为将第 y 位左边所有位的值按位取反，而其右边的所有位的值设为 0，因此整个运算的结果即为求出 `2^i` 的值，`i` 为在第 y 位右边 0 的个数。即为在 x 的二进制中从右向左连续为 0 的个数。

真是个神奇的代码，利用计算机补码的性质就能求出 x 对应的 k 值。膜拜发明者~  
有了这个神器，我们求出 A 数组中下标在区间 \[1, x\] 的元素的和就很简单了：

// 求出数组 A 中元素下标在区间 [1, x] 中的元素和
    int getSum(int x) {
        
    	int res = 0;
    	while (x > 0) {
        
    		res += c[x];
    		// 下标减去 x 对应的 k 值
    		x -= lowbit(x);
    	}
    }

那么 如果要求区间 \[a, b\] 的元素的和呢？其实答案就是区间 \[1, b\] 的元素和 减去 区间 \[1, a - 1\] 的元素和，用代码来描述：`getSum(a, b) = getSum(1, b) - getSum(1, a - 1);` 因为这里用的是闭区间，所以减的是 \[1, a - 1\] 而不是 \[1, a\]。下面是代码：

// 求出数组 A 中元素下标在区间 [1, x] 中的元素和
    int getSum(int x) {
        
    	int res = 0;
    	while (x > 0) {
        
    		res += c[x];
    		x -= lowbit(x);
    	}
    }
    
    // getSum 的重载函数，求出区间 [a, b] 的元素和
    int getSum(int a, int b) {
        
    	if (a > b) {
        
    		return 0;
    	}
    	return getSum(b) - getSum(a - 1);
    }

## 时间复杂度 ##

现在，我们来看一下求和操作的时间复杂度：我们会发现，当 C 数组的下标 x 为奇数的时候，一次 `x -= lowbit(x);`操作会将 x 对应的二进制的最后一个 1 变成 0，当 x 为偶数的时候，一次 `x -= lowbit(x)` 操作会去除 x 对应的二进制的最右边连续的 0 。举个例子：当 x = 7 的时候，执行 x -= lowbit(x) 之后，x = 6，再执行 x -= lowbit(x) 之后，x = 4。此时再执行 x -= lowbit(x) 的话， x = 0。一共执行了 3 次循环。而 7 对应的二进制为 111 。  
**即当 x 为奇数的时候，循环执行次数不会超过 x 对应二进制数字的位数**  
**当 x 为偶数的时候，循环执行次数同样不会超过 x 对应二进制数字的位数**  
**当 x 为 2 的正整数次幂的时候，循环只会执行 1 次，因为此时其对应的二进制数为：100000000… 也就是除了最左边一位数为 1，其余数全为 0。**  
因此，对于任意大于 0 的 x，求出区间 \[1, x\] 的元素和的循环执行次数不会超过 log(x) + 1  
**即用树状数组求区间的和的时间复杂度不会超过 log(x) 的整数值部分 + 1。其时间复杂度为 O(logn) 。**

## 元素更新 ##

接下来来看一下树状数组元素的更新，我们还是拿刚刚的图来看：  
![这里写图片描述][70 1]

假设我们现在要将元素 A\[1\] 的值加 1，那么我们需要处理的元素有 ：C\[1\]、C\[2\]、C\[4\]、C\[8\]。如图：

![这里写图片描述][70 2]

那么 1、2、4、8 这四个数的规律呢？和上面求和的一样：`1 + lowbit(1) = 2, 2 + lowbit(2) = 4, 4 + lowbit(4) = 8`  
于是更新树状数组元素的思路就出来了：

// 将位置为 pos 的树状数组元素值加上 addedValue，并且维护树状数组
    void plus_(int pos, int addedValue) {
        
    	while (pos < n + 1) {
        
    		c[pos] += addedValue;
    		pos += lowbit(pos);
    	}
    }

和求和一样，更新树状数组元素值的时间复杂度也为 O(logn)。

下面给出树状数组的完整代码：

/**
     * <!! 树状数组不能对值为 0 的下标进行操作，即当下标 x 值为 0 时， 
     *     x & (-x) 的值为 0 ，会造成死循环 !!> 
     */
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    const int MAXN = 100010;
    // 树状数组
    int treeArray[MAXN];
    
    int lowbit(int x) {
        
    	return x & (-x);
    }
    
    // 将位置为 pos 的树状数组元素值加上 addedValue，并且维护整个树状数组
    void plus_(int pos, int value) {
        
    	while (pos < MAXN) {
        
    		treeArray[pos] += value;
    		pos += lowbit(pos);
    	}
    }
    
    // 求区间 [1, n] 的元素和 
    int getSum(int n) {
        
    	if (n >= MAXN) {
        
    		exit(1);
    	}
    	int sum = 0;
    	while (n > 0) {
        
    		sum += treeArray[n];
    		n -= lowbit(n);
    	}
    	return sum;
    }
    
    // getSum 的重载函数，求出区间 [a, b] 的元素和
    int getSum(int a, int b) {
        
    	if (a > b) {
        
    		return 0;
    	}
    	return getSum(b) - getSum(a - 1);
    }
    
    int main() {
        
    	int n = 16;
    	for (int i = 1; i <= n; i++) {
        
    		plus_(i, 10);
    	}
    	cout << "当前的树状数组：" << endl;
    	for (int j = 1; j <= n; j++) {
        
    		cout << treeArray[j] << " ";
    	} 
    	cout << endl; 
    	for (int i = n; i > 0; i--) {
        
    		cout << "区间[1, " << i << "]" << "的元素和为：" << getSum(i) << endl; 
    	}
    	
    	return 0;
    }

我们从代码里面发现，**我们只用了一个树状数组 treeArray，并没有使用其他数组来储存每个元素，事实上我们并不需要其他数组，因为我们所有的操作都只针对和使用了树状数组，上文举例的 A 数组只是为了好理解而加上去的。**

来看看结果  
![这里写图片描述][70 3]

除了查询区间的和，树状数组还可以查询区间最大值、最小值等。模板代码已经给出了，对于不同的需求，需要不同的实现方式。

## 关于树状数组的下标 ##

最后，上文还留下了一个问题：我们在设置树状数组元素下标范围时设置的是 1~n，而并不是 0~n-1。原因主要是因为 lowbit 函数，你可以试试执行 lowbit(0) 的答案是什么，如果你没有写错的话，lowbit(0) 的值应该是 0 ，那么想像一下，如果我们要对下标为 0 的元素进行更新，**那么代码`pos += lowbit(0)` 的值永远不会改变，因此会陷入死循环**，对于求和操作也是同样的道理。  
对于有些特殊的情况，我们必须要使用下标 0 ，那么我们在对树状数组中下标为 0 的元素进行更新和求和的操作时都需要进行特殊处理，以防止死循环。

还需要注意的是，**一个储存基本数据类型的树状数组只能保存一种信息，比如这里的树状数组就只能保存对应区间的元素的和**，如果需要保存多种信息（区间最大值、区间最小值…），可以开多个树状数组，也可以用结构体来保存多种信息，然后开一个对应结构体类型的树状数组，并根据需求调整实现代码。

最后是一些习题：  
[Count of Smaller Number before itself][] 线段树可以求解，树状数组也可以求解，但是需要处理树状数组下标为 0 的情况  
[L3-002.堆栈][L3-002.]

好了，关于树状数组的一些思想的介绍就到这了，如果本文有帮到你，请不要吝啬你的赞，如果文章中有什么不正确的地方，还请多多指点  
谢谢观看。。。

[Link 1]: http://blog.csdn.net/hacker_zhidian/article/details/79382545
[70]: /images/20220530/c47f0efde9374427bd10a90366233979.png
[https_www.cnblogs.com_GeniusYang_p_5756975.html]: https://www.cnblogs.com/GeniusYang/p/5756975.html
[70 1]: /images/20220530/57e6d88eb4a0427bb99e7fef481d2b90.png
[70 2]: /images/20220530/13397f43bb274747bef95c946d7ef88b.png
[70 3]: /images/20220530/252c69eb7b1346d1b75c62a6869251c6.png
[Count of Smaller Number before itself]: http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/
[L3-002.]: https://www.patest.cn/contests/gplt/L3-002