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

想要理解这个结论。咱们需要先思考 i + lowbit(i) 到底意味着什么？
咱们假设 nums[i] = 109 。查看 nums[i] 能否通过不断加 lowbit(i) 更新到 c[128] 。即对应 [1, 128] 的区间。
109 的二进制为 01101101 。其不断加 lowbit(i) 的结果如下：

文章插图
观察上述结果。最终的确更新到了 128 。事实上。109 对应的二进制中。「最低位的 1 前面的 0」的位置分别是 1、4、7 。在其不断加 lowbit(i) 的过程中。最低位的 1 不断向前挪到最近的一个 0 。即 110、112、128 最低位的 1 分别为 1、4、7 。
因此咱们可以发现。不断加 lowbit(i) 的过程。即为将二进制中最低位的 1 不断向前挪到最近的一个 0 的过程。
回到前面的问题。「为什么令 i 不断加上 lowbit(i) 。即可更新所有对应区间覆盖了 nums[i] 的 c[x]」？
咱们假设 c[x] 对应的区间 [x - lowbit(x) + 1, x] 覆盖了 nums[i] 。且 c[x] 最低位 1 的位置为 pos 。则 nums[i] 的二进制形式在 [0, pos] 位中必定存在 1 。
此时分两种情况。若 nums[i] 二进制的 pos 位为 1 。则 nums[i] = x；若 nums[i] 二进制的 pos 位不为 1 。则 nums[i] 在不断加 lowbit(i) 的过程中。最低位的 1 一定会挪到 pos 位。即在加 lowbit(i) 的过程中达到 x 。由此可以证明之前的结论。
树形结构教学完树状数组的原理后。咱们再给出树状数组的树形图。来帮助各位进一步理解该数据结构。

文章插图
上图最下边一行为 nums 数组。代表 n 个叶节点。其上方为树状数组 c 。满足以下 5 条性质：
每个内部节点 c[x] 保存以它为根的子树中所有叶节点的和每个内部节点 c[x] 的值等于其子节点值的和每个内部节点 c[x] 的子节点个数为 lowbit(x) 的位数除树根外。每个内部节点 c[x] 的父节点为 c[x + lowbit(x)]树的深度为 O(log(n)) 。其中 n 表示 nums 数组的长度总结一下。树状数组支持在 O(log(n)) 的期间复杂度内「求数组区间和」或「更新数组中某一点的值」。其完整代码如下所示：
int n; // 树状数组长度vector<int> c;int lowbit(x) {return x & (-x);}void update(int x, int v) {for (int i = x; i <= n; i += lowbit(i)) c[i] += v;}int query(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += c[i];return res;}

文章插图
习题学习307. 位置和检索 - 数组可改写题目描述给你一个数组 nums。请你完成两类盘查。其中一类盘查要求更新数组下标对应的值。另一类盘查要求返回数组中某个范围内元素的总和。
实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值更新为 valint sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即。nums[left] + nums[left + 1], ..., nums[right]）示例
输入：["NumArray", "sumRange", "update", "sumRange"][[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]输出：[null, 9, null, 8]解释：NumArray numArray = new NumArray([1, 3, 5]);numArray.sumRange(0, 2); // 返回 9。sum([1,3,5]) = 9numArray.update(1, 2);// nums = [1,2,5]numArray.sumRange(0, 2); // 返回 8。sum([1,2,5]) = 8
提醒
1 <= nums.length <= 30000-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length最多调用 30000 次 update 和 sumRange 方法
解题思路该题属于树状数组的模板题。咱们来依次查看其要实现的函数。
首先是用 nums 数组初始化树状数组 c 。这时通常有两种操作。第一种是调用 n 次 update 函数。期间复杂度为 O(nlog(n)) 。代码如下：
for (int i = 1; i <= n; i++) update(i, nums[i]);第二种是根据之前的树形结构。每一个内部节点 c[x] 的值等于其所有子节点值的和。因此可以实现 O(n) 期间复杂度内的初始化。代码如下：
for (int i = 1; i <= n; i++) {c[i] += nums[i];int j = i + lowbit(i);if (j <= n) c[j] += c[i];}下一步是第二个函数。将 nums[i] 的值更新为 val 。而之前树状数组中的 update 操作为将 nums[i] 的值增加 val 。因此咱们需要「保存」或「求出」nums[i] 的目前值。再令其增加 val - nums[i] 即可。
最后是第三个函数。求 nums 数组在 [i, j] 上的区间和。之前树状数组的 query 操作可以求 [1, x] 的区间和。因此 [i, j] 的区间和等于 query(j) - query(i - 1) 。
至此本题结束。具体代码如下。代码实现
class NumArray {public:int n;vector<int> c;int lowbit(int x) {return x & (-x);}void update_c(int x, int v) {for (int i = x; i <= n; i += lowbit(i)) c[i] += v;}int query(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += c[i];return res;}NumArray(vector<int>& nums) {n = nums.size();c.clear();c.resize(n + 1, 0);for (int i = 1; i <= n; i++) {c[i] += nums[i-1];int j = i + lowbit(i);if (j <= n) c[j] += c[i];}}void update(int index, int val) {val -= query(index + 1) - query(index);update_c(index + 1, val);}int sumRange(int left, int right) {return query(right + 1) - query(left);}};