【树状数组】LeetCode 307. Range Sum Query - Mutable
问题的提出
有一个数组 nums[0 . . . N-1]
,我们希望能提供如下两个功能:
- 功能1:求出前
i
个元素的和sum
- 功能2:改变某个元素的值,即
nums[i] = x
请参考 LeetCode 307. Range Sum Query - Mutable
一般情况下,功能1的时间复杂度为O(N)
,功能2的时间复杂度为O(1)
。
如果要改进功能1时间复杂度,我们可以依赖一个前缀和数组sum
,用于记录前 i
个元素的和,即 sum[i] = nums[0] + nums[1] + ... + nums[i]
。但此时,功能2的时间复杂度变为了O(N)
,因为需要去维护数组 sum
。
树状数组就是用来平衡这两个时间复杂度的,可以使得功能1和功能2的时间复杂度都为O(logN)
。
引子 —— 一个位运算
获取数字 X
的最低比特位的计算式f(X)= X & -X
这个位运算举几个例子就大致明白了,具体证明也很简单,因为负数补码是正数按位取反再加1。实在不明白记住就行了,在此不再偏题赘述。
树状数组方法
创建数组BITree(图片中对应为数组C)
对于数组 a
,我们设一个数组 BITree
,有 BITree[i]=a[i-f(i)+1]+a[i-f(i)+2]+...+a[i]
。
其中f(i)
就是取最低比特位的函数。
这里的数组a
和BITree
都是从1
开始算的,把索引0
位置置零即可!
下图的C
即为数组BITree
,lowbit(i)
即为f(i)
计算i到j的和
计算方法:
sum(i,j)=sum(j)-sum(i-1)
代码如下:
public int sumRange(int i, int j) {
i++;
j++;
return sum(j) - sum(i - 1);
}
上述的i++
和j++
是索引0到索引1的转化过程。
接下来就要提供一个计算前缀和sum(index)
的方法。
具体算法是
public int sum(int index) {
int res = 0;
while (index > 0) {
res += BITree[index];
index = index - (index & -index);
}
return res;
}
即
其中
例如
sum的构成证明
按照BITree
的定义,展开每一项即可
求和复杂度证明
为了证明sum(i,j)
复杂度是O(logN)
,只需要证明sum(N)
复杂度为O(logN)
,证明思路为每次N
都去掉了最低的二进制位,故最多循环O(logN)
次。
更新算法
先更新a[i]
,再调用updateBIT
方法更新BITree
数组
public void update(int i, int val) {
i++;
int diff = val - a[i];
a[i]=val;
updateBIT(i, diff);
}
这里又涉及到判断BITree
中哪些项需要更新。
具体代码如下:
private void updateBIT(int i, int diff){
while (i < arr.length) {
BITree[i] += diff;
i = i + (i & (-i));
}
}
更新规则如下:
更新过程的证明
采用数学归纳法
一个例子
LeetCode 307. Range Sum Query - Mutable 的代码解答
class NumArray {
private int[] a;
private int[] BITree;
public NumArray(int[] nums) {
a = new int[nums.length + 1];
System.arraycopy(nums, 0, a, 1, nums.length);
BITree = new int[nums.length + 1];
// 初始化BITree数组
int[] sum = new int[nums.length + 1];
for (int i = 1; i < sum.length; i++) {
updateBIT(i, a[i]);
}
}
public void update(int i, int val) {
i++;
int diff = val - a[i];
a[i]=val;
updateBIT(i, diff);
}
private void updateBIT(int i, int diff){
while (i < a.length) {
BITree[i] += diff;
i = i + (i & (-i));
}
}
public int sumRange(int i, int j) {
i++;
j++;
return sum(j) - sum(i - 1);
}
private int sum(int index) {
int res = 0;
while (index > 0) {
res += BITree[index];
index = index - (index & -index);
}
return res;
}
参考链接
推荐阅读
-
【leetcode】307. Range Sum Query - Mutable
-
leetcode 307. Range Sum Query - Mutable
-
Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable (线段树Segment Tree)-超详细Python
-
【树状数组】LeetCode 307. Range Sum Query - Mutable
-
leetcode-307. Range Sum Query - Mutable]()
-
数据结构线段树介绍与笔试算法题-LeetCode 307. Range Sum Query - Mutable--Java解法
-
LeetCode 307. Range Sum Query - Mutable (范围求和查询)
-
LeetCode------Range Sum Query - Mutable
-
LeetCode-307. Range Sum Query - Mutable以及线段树总结