树状数组图文详解

单点更新，区间查询

假设有一个数组，对他大量的修改和查询，修改的是数组中某一个元素的值，查询的是数组中任意一个区间的和。对于修改比较简单，时间复杂度是 O(1) ，而查询的时间复杂度是 O(n) 。有同学可能会说使用前缀和来优化，前缀和查询的时间复杂度确实是 O(1) ，但如果我们修改某一个元素的时候，前缀和后面的值也都要修改，时间复杂度是  O(n) 。那么我们综合一下，有没有一种方式可以让修改和查询时间复杂度降一个数量级呢？有的，那就是树状数组，他的修改和查询时间复杂度都是 O(logn) ，综合来看还是不错的。如下图所示，他就是一个树状数组，其中数组 a[] 是原始数组，数组 c[] 是树状数组。

我们令树状数组每个位置存的是子节点值的和，则有：

通过上面的公式可以发现一个规律就是：

比如 c[6] ， 6 的二进制是 (110) ，最右边有 1 个 0 ，那么 k 就等于 1 ，所以：

在比如 c[4] ， 4 的二进制是 (100) ，最右边有 2 个连续的 0 ，那么 k 就等于 2 ，所以：

通过上面的图我们可以发现，在树状数组 c[i] 中，如果 i 是奇数， c[i] 就在第 0 层，也就是树状数组的叶子节点，并且  c[i] = a[i] 。如果 i 不是奇数，那么在 i 的二进制位中，他右边有几个 0 ， c[i] 就在第几层。我们定义函数 int lowBit(int x) 表示只保留 x 的二进制中最右边的 1 ，其他位置全部变为 0 ，比如：

函数 int lowBit(int x) 的代码如下：

这个很好理解，比如数字 12 和 -12 ，他们的二进制如下，只要他们进行 & 运算就是我们想要的结果。

令 s[i] 表示元素数组 a 的前 i 项和，通过上面的图可以找出 s 和 c 的关系如下：

通过上面等式的关系我们可以得出：

这里的 k1，k2，k3，……，kn 都是 2 的 k 次方，实际上就是不断的抹去 i 的二进制中右边的 1 ，直到 i 变成 0 为止。比如数字 7 ，他的二进制是 111 ，所以 s[111]=c[111]+c[110]+c[100]（这里的数字是二进制表示），也就是 s[7]=c[7]+c[6]+c[4] 。

这个就是求和，如果要计算数组  a 区间 [left,right] 的和，可以像下面这样调用。

树状数组的求和我们知道了，那么修改呢（这里先讨论单点修改）？如果树状数组的一个节点值被修改了，那么他的父节点值都要改变，如下图所示，当 a[5] 的值修改后， c5 ，c6 以及 c8 都要修改。

如果要更改 c[i] 的值，只需要找到 c[i] 的父节点以及他父节点的父节点，……，一直往上走，直到根节点，全部修改即可。通过图 1-8 我们可以发现， c[i] 的父节点就是 c[i+lowBit(i)] ，所以我们需要以 c[i] 为起点，通过循环不断的往上找父节点然后修改，来看下树状数组的完整代码：

区间更新，单点查询

对于数组更新和查找可以分为下面几类：

• 单点更新，单点查询

• 单点更新，区间查询

• 区间更新，单点查询

• 区间更新，区间查询

对于“单点更新，单点查询”，原始数组就可以做，不需要构建树状数组。而“单点更新，区间查询”我们上面刚介绍过，这里来看下“区间更新，单点查询”。如果想要区间更新需要构建差分数组，在前面 差分数组 中我们讲过，如果要更新原始数组区间的值，只需要更新差分数组两边的值即可。其中差分数组的前缀和就是数组 a 中某个元素的值，来看下代码：

区间更新，区间查询

区间更新可以使用差分数组，那么区间查询呢？假设求数组 a 的前 n 项和，我们来看下公式推导，如下图所示。

a 是原数组， d 是差分数组，这里我们需要构建两个树状数组，其中 d1[i] = d[i]，d2[i] = d[i]*(i-1); 。

区间更新和区间查询除了使用树状数组还可以使用线段树，线段树不光能区间求和，还可以求区间最大值，区间最小值，功能要比树状数组更强大。

原文链接：https://wansuanfa.com/index.php/2023/05/23/%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84/

学习更多数据结构，可以在我的文集管理中查看。