LeetCode 307 Range Sum Query - Mutable（范围和查询-可变）

翻译

给定一个整型数组nums，找出在索引i到j之间的元素的和（i <= j），包括i 和 j。

函数update(i, val)用于修改在索引i的元素为val。

例如，
给定nums = [1, 3, 5]

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

备注：
该数组只能被update函数修改。
你可以假设update和sumRange函数的调用是均匀分布的。

原文

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:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

分析

原始方法

记得之前也做过类似这么一道题，不过最简单的那种for循环并不能解决问题。那个题目最后会给很大的数据量，要用哈希表进行分区段的数据保存。所以我也以为这道题会是这样，但我用for循环居然也通过了，所以就懒得再写了。

class NumArray {
private:
    vector<int> numsV;
public:
    NumArray(vector<int> &nums) {
        numsV = nums;
    }

    void update(int i, int val) {
        numsV[i] = val;
    }

    int sumRange(int i,int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) {
            sum += numsV[k];
        }
        return sum;
    }
};

开方分解

除了上面所说的用哈希表外，还可以用题中给出的开方分解的方式。

这个思想如下图所示，数组中共有9个元素，我们可以开方得到3，并以此分成3块。当我们需要求RSQ（1,7）时，那就是b[1]和值，加上前面和后面的快的部分值。

class NumArray {
private:
    int len;
    vector<int> numsV;
    vector<int> b;
public:
    NumArray(vector<int> &nums) {
        numsV = nums;
        if (nums.size() == 0)
            len = 0;
        else {
            double l = sqrt(nums.size());
            len = (int) ceil(nums.size() / l);
            b = vector<int>(len);
            for (int i = 0; i < numsV.size(); i++) {
                b[i / len] += numsV[i];
            }
        }
    }

    void update(int i, int val) {
        int b_l = i / len;
        b[b_l] = b[b_l] - numsV[i] + val;
        numsV[i] = val;
    }

    int sumRange(int i,int j) {
        if (len == 0)
            return 0;
        int sum = 0;
        int startBlock = i / len;
        int endBlock = j / len;
        if (startBlock == endBlock) {
            for (int k = i; k <= j; k++) {
                sum += numsV[k];
            }
        } else {
            for (int k = i; k <= (startBlock + 1) * len - 1; k++)
                sum += numsV[k];
            for (int k = startBlock + 1; k <= endBlock - 1; k++)
                sum += b[k];
            for (int k = endBlock * len; k <= j; k++)
                sum += numsV[k];
        }
        return sum;
    }
};

• 时间复杂度
  
  • 初始化阶段为$O(n)$，update阶段为$O(1)$，sumRange阶段为$O(\sqrt{n})$
  • 对于范围和查询来说，我们必须计算大约$3\sqrt{n}$个元素。在这种情况下的范围包括$\sqrt{n} - 2$个块，也意味着需要$\sqrt{n} - 2$次操作。除此之外，还需要计算边界的两个块的元素，这需要另外$2（\sqrt{n} - 1）$次操作。综合来看，共需要的操作大概是$3\sqrt{n}$次。
• 空间复杂度
  
  • $O(\sqrt{n})$
  • 我们需要额外的$\sqrt{n}$快存储区域来保存所有快（block）的和

代码

哎，记得之前也做过类似这么一道题，不过最简单的那种for循环并不能解决问题。原文题目最后会给很大的数据量，要求用哈希表进行分区段的数据保存。所以我也以为这道题会是这样，但我用for循环居然也通过了，所以就懒得再写了。