欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【树状数组】LeetCode 307. Range Sum Query - Mutable

程序员文章站 2022-07-13 11:03:25
...

问题的提出

有一个数组 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)就是取最低比特位的函数。
这里的数组aBITree都是从1开始算的,把索引0位置置零即可!
下图的C即为数组BITreelowbit(i)即为f(i)
【树状数组】LeetCode 307. Range Sum Query - Mutable

计算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(k)=BITree[n1]++BITree[nm]sum(k)=BITree[n_1]+\cdots+BITree[n_m]
其中
nm=k,ni1=nif(ni),n1=f(n1)n_m=k, n_{i-1}=n_i-f(n_i), n_1=f(n_1)
例如
sum(6)=BITree[6]+BITree[4]sum(6)=BITree[6]+BITree[4]

sum的构成证明

按照BITree的定义,展开每一项即可
【树状数组】LeetCode 307. Range Sum Query - Mutable

求和复杂度证明

为了证明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

更新过程的证明

采用数学归纳法
【树状数组】LeetCode 307. Range Sum Query - Mutable
【树状数组】LeetCode 307. Range Sum Query - Mutable
【树状数组】LeetCode 307. Range Sum Query - Mutable
【树状数组】LeetCode 307. Range Sum Query - Mutable

一个例子

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;
    }

参考链接

【1】https://www.jianshu.com/p/455fd78637be
【2】北大 acm 暑期课