LeetCode 307. Range Sum Query - Mutable (范围求和查询)

原题

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.

Reference Answer

思路分析

解法一：

用最愚蠢的 brute force，能通过，就是效率低，代码如下：

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即可，参见代码如下：

Code

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

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
        

同样是利用分块区域和的思路，下面这种方法使用了一种新的数据结构，叫做 树状数组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, 7, 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个数字之和了，从而也就能求出任意区间之和了，参见代码如下：

Note

• 规律不是很好找，这道题还是建立在本身就知道这种排列结构比较容易做；
• 注意内层循环中while nums[after_index] <= nums[pre_index]:，必须是小于等于，不然不能得到正确结果，做题时候在这浪费了不少时间。

参考文献

[1] http://www.cnblogs.com/grandyang/p/4985506.html