307. Range Sum Query - Mutable

 

Given an integer array nums , find the sum of the elements between indices i and j ( ij ), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

 

这道题是之前那道 Range Sum Query - Immutable 的延伸,之前那道题由于数组的内容不会改变,所以我们只需要建立一个累计数组就可以支持快速的计算区间值了,而这道题说数组的内容会改变,如果我们还是用之前的方法建立累计和数组,那么每改变一个数字,之后所有位置的数字都要改变,这样如果有很多更新操作的话,就会十分不高效,估计很难通过吧。But,被 OJ 分分钟打脸, brute force 完全没有问题啊,这年头,装个比不容易啊。直接就用个数组 data 接住 nums,然后要更新就更新,要求区域和,就遍历求区域和,就这样 naive 的方法还能 beat 百分之二十多啊,这不科学啊,参见代码如下:

 

解法一:

class NumArray {
public:
    NumArray(vector<int> nums) {
        data = nums;
    }
    
    void update(int i, int val) {
        data[i] = val;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; ++k) {
            sum += data[k];
        }
        return sum;
    }
    
private:
    vector<int> data;
};

 

咳咳,下面就开始闪亮的装比时间了,光芒必将盖过坂本大佬。上面的方法最大的问题,就是求区域和不高效,如果数组很大很大,每次求一个巨型的区间的和,都要一个一个的遍历去累加,累啊~但是一般的累加数组又无法应对这里的 update 操作,随便修改一个数字的话,那么其之后的所有累加和都会发生改变。所以解决方案就是二者折中一下,分块累加,各不干预。就是将原数组分为若干块,怎么分呢,这里就让每个 block 有 sqrt(n) 个数字就可以了,这个基本是让 block 的个数跟每个 blcok 中数字的个数尽可能相同的分割方法。然后我们就需要一个大小跟 block 个数相同的数组,来保存每个 block 的数字之和。在需要更新的时候,我们就先确定要更新的位置在哪个 block 里,然后只更新该 block 的和。而对于求区域和操作,我们还是要分别确定i和j分别属于哪个 block,若属于同一个 block,那么直接遍历累加即可,若属于不同的,则先从i累加到该 blcok 的末尾,然后中间横跨的那些 block 可以直接将和累加,对于j所在的 blcok,则从该 block 的开头遍历累加到j即可,参见代码如下:

 

解法二:

class NumArray {
public:
    NumArray(vector<int> nums) {
        if (nums.empty()) return;
        data = nums;
        double root = sqrt(data.size());
        len = ceil(data.size() / root);
        block.resize(len);
        for (int i = 0; i < data.size(); ++i) {
            block[i / len] += data[i];
        }
    }
    
    void update(int i, int val) {
        int idx = i / len;
        block[idx] += val - data[i];
        data[i] = val;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        int start = i / len, end = j / len;
        if (start == end) {
            for (int k = i; k <= j; ++k) {
                sum += data[k];
            }
            return sum;
        }
        for (int k = i; k < (start + 1) * len; ++k) {
            sum += data[k];
        }
        for (int k = start + 1; k < end; ++k) {
            sum += block[k];
        }
        for (int k = end * len; k <= j; ++k) {
            sum += data[k];
        }
        return sum;
    }
    
private:
    int len;
    vector<int> data, block;
};

 

同样是利用分块区域和的思路,下面这种方法使用了一种新的数据结构,叫做 树状数组Binary Indexed Tree,又称 Fenwick Tree,这是一种查询和修改复杂度均为 O(logn) 的数据结构。这个树状数组比较有意思,所有的奇数位置的数字和原数组对应位置的相同,偶数位置是原数组若干位置之和,假如原数组 A(a1, a2, a3, a4 …),和其对应的树状数组 C(c1, c2, c3, c4 …)有如下关系:

C1 = A1

C2 = A1 + A2

C3 = A3

C4 = A1 + A2 + A3 + A4

C5 = A5

C6 = A5 + A6

C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

那么是如何确定某个位置到底是有几个数组成的呢,原来是根据坐标的最低位 Low Bit 来决定的,所谓的最低位,就是二进制数的最右边的一个1开始,加上后面的0(如果有的话)组成的数字,例如1到8的最低位如下面所示:

坐标          二进制       最低位

1               0001          1

2               0010          2

3               0011          1

4               0100          4

5               0101          1

6               0110          2

7               0111          1

8               1000          8

最低位的计算方法有两种,一种是 x&(x^(x–1)),另一种是利用补码特性 x&-x。

这道题我们先根据给定输入数组建立一个树状数组 bit,比如,对于 nums = {1, 3, 5, 9, 11, 13, 15, 17},建立出的 bit 数组为:

bit -> 0 1 4 5 18 11 24 15 74

注意到我们给 bit 数组开头 padding 了一个0,这样我们在利用上面的树状数组的性质时就不用进行坐标转换了。可以发现bit数组中奇数位上的数字跟原数组是相同的,参见上面标记蓝色的数字。偶数位则是之前若干位之和,符合上图中的规律。

现在我们要更新某一位数字时,比如将数字5变成2,即 update(2, 2),那么现求出差值 diff = 2 - 5 = -3,然后我们需要更新树状数组 bit,根据最低位的值来更新后面含有这一位数字的地方,一般只需要更新部分偶数位置的值即可。由于我们在开头 padding了个0,所以我们的起始位置要加1,即 j=3,然后现将 bit[3] 更新为2,然后更新下一位,根据图中所示,并不是 bit[3] 后的每一位都需要更新的,下一位需要更新的位置的计算方法为 j += (j&-j),这里我们的j是3,则 (j&-j) = 1,所以下一位需要更新的是 bit[4],更新为15,现在j是4,则 (j&-j) = 4,所以下一位需要更新的是 bit[8],更新为71,具体的变换过程如下所示:

0 1 4 5 18 11 24 15 74

0 1 4 2 18 11 24 15 74

0 1 4 2 15 11 24 15 74

0 1 4 2 15 11 24 15 71

接下来就是求区域和了,直接求有些困难,我们需要稍稍转换下思路。比如若我们能求出前i-1个数字之和,跟前j个数字之和,那么二者的差值就是要求的区间和了。所以我们先实现求前任意i个数字之和,当然还是要利用树状数组的性质,此时正好跟 update 函数反过来,我们的j从位置i开始,每次将 bit[j] 累加到 sum,然后更新j,通过 j -= (j&-j),这样就能快速的求出前i个数字之和了,从而也就能求出任意区间之和了,参见代码如下:

 

解法三:

class NumArray {
public:
    NumArray(vector<int> nums) {
        data.resize(nums.size());
        bit.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); ++i) {
            update(i, nums[i]);
        }
    }

    void update(int i, int val) {
        int diff = val - data[i];
        for (int j = i + 1; j < bit.size(); j += (j&-j)) {
            bit[j] += diff;
        }
        data[i] = val;
    }

    int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }    

    int getSum(int i) {
        int res = 0;
        for (int j = i; j > 0; j -= (j&-j)) {
            res += bit[j];
        }
        return res;
    }

private:
    vector<int> data, bit;
};

 

下面这种方法使用了 线段树 Segment Tree 来做,对线段树不是很了解的童鞋可以参见 网上这个帖子,在博主看来,线段树就是一棵加了些额外信息的满二叉树,比如可以加子树的结点和,或者最大值,最小值等等,这样,当某个结点的值发生变化时,只需要更新一下其所有祖先结点的信息,而并不需要更新整棵树,这样就极大的提高了效率。比如对于 [1 3 5 7] 这个数组,我们可以根据其坐标划分,组成一个线段树:

           [0, 3]
             16
       /            \
    [0, 1]        [2, 3]
      4             12
   /     \       /     \
[0, 0] [1, 1] [2, 2] [3, 3]
   1      3      5      7

其中,中括号表示是区间的范围,下方的数字是区间和,这样如果我们如果要更新区间 [2, 2] 中的数字5,那么之后只要再更新 [2, 3] 和 [0, 3] 两个区间即可,并不用更新所有的区间。而如果要求区间和,比如 [1, 3] 的话,那么只需要加上这两个区间 [1, 1] 和 [2, 3] 的和即可,感觉跟解法二的核心思想很类似。

将线段树的核心思想理解了之后,我们就要用它来解题了。这里,我们并不用建立专门的线段树结点,因为博主十分的不喜欢在 Solution 类中新建其他类,博主追求的是简约时尚的代码风格,所以我们可以只用一个数组来模拟线段树。大小是多少呢,首先肯定要包换 nums 中的n个数字了,对于一个有n个叶结点的平衡的满二叉树,其总结点个数不会超过2n个,不要问博主怎么证明,因为我也不会。但你可以任意举例子来验证,都是正确的。所以我们用一个大小为 2n 的 tree 数字,然后就要往里面填数字了。填数字的方式先给 tree 数组的后n个数字按顺序填上 nums 数字,比如对于 nums = [1 3 5 7],那么 tree 数组首先填上:

_ _ _ _ 1 3 5 7

然后从 i=3 开始,每次填上 tree[2n] + tree[2n+1],那么以此为:

_ _ _ 12 1 3 5 7

_ _ 4 12 1 3 5 7

_ 16 4 12 1 3 5 7

那么最终的 tree 数组就是 [0 16 4 12 1 3 5 7],tree[0] 其实没啥作用,所以不用去管它。

接下来看 update 函数,比如我们想把5换成2,即调用 update(2, 2),由于 nums 数组在 tree 数组中是从位置n开始的,所以i也要加n,变成了6。所以先把 tree[6] 换乘2,那么此时 tree 数组为:

0 16 4 12 1 3 2 7

然后还要更新之前的数字,做法是若i大于0,则进行 while 循环,因为我们知道 tree 数组中i位置的父结点是在 tree[i/2],所以我们要更新 tree[i/2],那么要更新父结点值,就要知道左右子结点值,而此时我们需要知道i是左子结点还是右子结点么?其实可以使用一个小 trick,就是对于结点i,跟其成对儿的另一个结点位置是 i^1,根据异或的性质,当i为奇数,i^1 为偶数,当i为偶数,i^1 为奇数,二者一直成对出现,这样左右子结点有了,直接更新父结点 i/2 即可,然后i自除以2,继续循环。tree数组的之后变化过程为:

0 16 4 9 1 3 2 7

0 13 4 9 1 3 2 7

13 13 4 9 1 3 2 7

可以看到,tree[0] 也被更新,但其实并没有什么卵用,不用理它。

接下来就是求区域和了,比如我们要求 sumRange(1, 3),对于更新后的数组 nums = [1 3 2 7],我们可以很快算出来,是 12。那么对于 tree = [13 13 4 9 1 3 2 7],我们如何计算呢。当然还是要先进行坐标变换,i变为5,j变为7。然后进行累加,我们的策略是,若i是左子结点,那么跟其成对儿出现的右边的结点就在要求的区间里,则此时直接加上父结点值即可,若i是右子结点,那么只需要加上结点i本身即可。同理,若j是左子结点,那么只需要加上结点j本身,若j是右子结点,那么跟其成对儿出现的左边的结点就在要求的区间里,则此时直接加上父结点值即可。具体的实现方法是,判断若i是奇数,则说明其是右子结点,则加上 tree[i] 本身,然后i自增1;再判断若j是偶数,则说明其是左子结点,则加上 tree[j] 本身,然后j自减1。那么你可能有疑问,i是偶数,和j是奇数的情况就不用处理了么,当然不是,这两种情况都是要加父结点的,我们可以到下一轮去加,因为每一轮后,i和j都会除以2,那么i一定会有到奇数的一天,所以不用担心会有值丢失,一定会到某一个父结点上把值加上的,参见代码如下:

 

解法四:

class NumArray {
public:
    NumArray(vector<int> nums) {
        n = nums.size();
        tree.resize(n * 2);
        buildTree(nums);
    }

    void buildTree(vector<int>& nums) {
        for (int i = n; i < n * 2; ++i) {
            tree[i] = nums[i - n];
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    void update(int i, int val) {
        tree[i += n] = val;
        while (i > 0) {
            tree[i / 2] = tree[i] + tree[i ^ 1];
            i /= 2;
        }
    }

    int sumRange(int i, int j) {
        int sum = 0;
        for (i += n, j += n; i <= j; i /= 2, j /= 2) {
            if ((i & 1) == 1) sum += tree[i++];
            if ((j & 1) == 0) sum += tree[j--];
        }
        return sum;
    }    

private:
    int n;
    vector<int> tree;
};

 

讨论:通过介绍上面四种不同的方法,我们应该如何处理可变的区间和问题有了深刻的认识了。除了第一种 brute force 的方法是无脑遍历之外,后面三种方法其实都进行了部分数字的和累加,都将整体拆分成了若干的小的部分,只不过各自的拆分方法各不相同,解法二是平均拆分,解法三树状数组是变着花样拆分,解法四线段树是二分法拆分,八仙过海,各显神通吧。

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/307

 

类似题目:

Range Sum Query 2D - Mutable

Range Sum Query 2D - Immutable

Range Sum Query - Immutable

 

参考资料:

https://leetcode.com/problems/range-sum-query-mutable/

https://leetcode.com/problems/range-sum-query-mutable/discuss/75763/7ms-Java-solution-using-bottom-up-segment-tree

https://leetcode.com/problems/range-sum-query-mutable/discuss/75785/Share-my-c%2B%2B-solution%3A-1700ms-using-tree-array

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation