数据结构与算法分析面试必考的算法与数据结构详解 _经验知识

文章插图
树状数组。经典树形数据结构之一。代码很短。但其蕴含的算法思想却非常精妙。可以这么说。刷算法题却不懂树状数组。那绝对算是一大遗憾。
树状数组。常用于高效处理「一个数组的更新以及前缀和的求取」。
具体来探讨。其常用于高效求解如下问题：给定一个长度为 n 的数组 nums 。需要支持两类操作：操作 1: 将 nums[i] 的数值增加 v操作 2: 求取 nums[1] + nums[2] + ... + nums[i] 的值对于上述问题。如果咱们选用直接的做法。则操作 1 的期间复杂度为 O(1) 。操作 2 的期间复杂度为 O(n) 。假如一共有 q 次操作。则总的期间复杂度为 O(qn) 。
而如果使用树状数组来求解。则操作 1 和操作 2 的期间复杂度均为 O(log(n)) 。假如一共有 q 次操作。则总的期间复杂度为 O(qlog(n)) 。对比之前的做法。树状数组的解法在期间复杂度上有根本性的优势。而这也正是咱们学习该算法的原因。

文章插图
树状数组树状数组加快运算的关键。在于对二进制的进一步挖掘。因此我们第一个步来回忆一下二进制。
以正整数 29 为例。其二进制为 11101 。因此 29 可以根据其二进制进一步表示为：

文章插图
根据这一特点。咱们可以重新思考之前的「操作 2」。即如何超快求取数组 [1, 29] 的和？
仿照之前对 29 的二进制拆分。咱们也完全可以将 [1, 29] 拆分成如下四个区间的相加：

文章插图
观察上述四个区间。可以发现四个区间的长度依次为 2^4、2^3、2^2、2^0 。并且对于每一个区间来探讨。其区间长度恰好等于「区间右端点二进制中最低位的 1 对应的数值」。以区间 [2^4 + 1,2^4 +2^3] 为例。其区间长度为 2^3 。而其区间右端点为 2^4 +2^3 。二进制为 11000 。其中最低位的 1 在第 3 位。对应的数值为 2^3 。恰好等于其区间长度。
lowbit(x)为了更好地形式化描述上述观察。咱们引入 lowbit(x) 函数。表示「x 二进制中最低位的 1 对应的数值」。例如 29 。其二进制为 11101 。则最低位的 1 在第 0 位。对应的数值为 2^0 。即 lowbit(29) = 1 。再比如 16 。其二进制为 10000 。则最低位的 1 在第 4 位。对应的数值为 2^4 。即 lowbit(16) = 16 。
理解完 lowbit(x) 的功能后。咱们给出其代码形式：int lowbit(x) {return x & (-x);}代码非常短。但想要理解却需要一些原码、补码的知识。简单来探讨。在计算机中。所有整数都是用补码的形式来存放的。对于正整数 x 来探讨。其补码形式就是其二进制的形式。但对于负数 -x 来探讨。咱们需要将 x 的二进制形式按位取反再加 1 。
依旧以 29 和 16 为例。并且用 8 位二进制的形式来表示：

文章插图
原理教学有了 lowbit(x) 函数。咱们可以更容易地表示 [1, 29] 的拆分形式：

文章插图
由此一来。咱们可以更容易地发现四个区间的长度依次为 lowbit(16)、lowbit(24)、lowbit(28)、lowbit(29) 。即 2^4、2^3、2^2、2^0 。
到了这一步。咱们便推导出了树状数组 c 的含义。即 c[x] 表示区间 [x - lowbit(x) + 1,x] 的和。即：

文章插图
因此 [1, 29] 的和可以表示为：

文章插图
除此之外。咱们还可以发现：

文章插图
由此。咱们可以得到树状数组关于操作 2 。即求取 [1, x] 区间和的代码：
int query(int x) {int res = 0;// 当 i 等于 0 时。退出 for 循环for (int i = x; i; i -= lowbit(i)) res += c[i];return res;}至此。还剩下一个函数未教学。即对于操作 1 来探讨。当 nums[i] 的数值增加了 v 。树状数组 c 该如何变化？
由于 c[x] 表示区间 [x - lowbit(x) + 1, x] 的和。因此咱们只要将所有覆盖了 nums[i] 的 c[x] 均加上 v 即可。由此问题转变为了「如何寻找到所有覆盖了 nums[i] 的 c[x]」？
寻找的方法非常简单。咱们先直接给出代码：
void update(int x, int v) {// n 为树状数组的长度for (int i = x; i <= n; i += lowbit(i)) c[i] += v;}观察上述代码。咱们可以发现只要令 i 不断加上 lowbit(i) 。即可更新所有对应区间覆盖了 nums[i] 的 c[x] 。