题目描述

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

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

1. 数组仅可以在 update 函数下进行修改。
2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – Prefix sum

我们可以预先计算出前缀和存储在数组中，prefix[i] = num[0]+…+nums[i]。这样，当需要求得范围[i,j]的和时，我们可以通过prefix[j]-prefix[i-1]在O(1)的时间计算出结果。但是当nums[i]发生更新操作，那么我们不得不重新计算prefix[i]之后的前缀和，时间复杂度为O(n)。

全部代码如下：

class NumArray {
    int[] nums;
    int[] prefix;

    public NumArray(int[] nums) {
        this.nums = nums;
        prefix = new int[nums.length];


        for (int i = 0; i < nums.length; i++) {
            if (i == 0)
                prefix[i] = nums[0];
            else
                prefix[i] = prefix[i - 1] + nums[i];
        }
    }

    public void update(int i, int val) {
        nums[i] = val;
        for (int j = i; j < nums.length; j++) {
            if (j == 0)
                prefix[j] = nums[j];
            else
                prefix[j] = prefix[j - 1] + nums[j];
        }
    }

    public int sumRange(int i, int j) {
        if (i == 0)
            return prefix[j];
        return prefix[j] - prefix[i - 1];
    }
}

解法2 – Fenwick Tree（树状数组）

Fenwick Tree也称为树状数组，它可以在O(logn)的时间得到任意前缀和，并同时支持在O(logn)时间内支持动态单点值的修改。空间复杂度O(n)。为了实现Fenwick Tree，我们需要一个函数lowbit(x)，他是用来求得数值x最低位第一个1所代表到数值，例如x = 0110，lowbit(x) = 0010; x = 0101, lowbit(x) = 0001。

该数据结构有两个操作，一个是update(i, delta)用于更新第i个元素，表示将第i个元素增加delta；一个是query(i)，表示求得前i个数的和。

当Tree建立好后，更新操作的时间复杂度为O(logn)，这比解法1的O(n)要高效很多。全部代码如下：

class NumArray {
    FenwickTree fenwickTree;
    int[] nums;

    class FenwickTree {
        int[] sums;

        FenwickTree(int[] nums) {
            sums = new int[nums.length + 1];

            for (int i = 0; i < nums.length; i++) {
                update(i, nums[i]);
            }
        }

        int lowbit(int x) {
            return x & (-x);
        }

        // i start with 0
        void update(int i, int delta) {
            i++;
            while (i < sums.length) { // 当i>=sums.length就到了跟节点
                sums[i] += delta;
                i += lowbit(i); // 更新i指向父节点
            }
        }

        // i start with 0
        int query(int i) {
            i++;
            int sum = 0;

            while (i > 0) {
                sum += sums[i];
                i -= lowbit(i);
            }

            return sum;
        }
    }

    public NumArray(int[] nums) {
        fenwickTree = new FenwickTree(nums);
        this.nums = nums;
    }

    public void update(int i, int val) {
        int delta = val - nums[i];
        fenwickTree.update(i, delta);
        nums[i] = val; // 这里一定要更新nums，否则下次计算delta就不对了
    }

    public int sumRange(int i, int j) {
        return fenwickTree.query(j) - fenwickTree.query(i - 1);
    }
}

解法3 – 线段树（待续）