[LeetCode] 307. Range Sum Query - Mutable

[grandyang]

 

Given an integer array nums , find the sum of the elements between indices i and j ( i ≤ j ), 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 同步地址：

#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 题目讲解汇总(持续更新中...)