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

可以先参考数组不发生变动时的题目。

这里的难度在于数组可以在中间出现变动，那么面对大容量数组的时候如何选择一个合适的数据结构及很重要。

思路一：map缓存

最开始我们有两种直观的想法，一种是在插入时同时更新后面所有的和，这意味着O(n)的插入复杂度和O(1)的读取复杂度。我决定选择第二种方式，也就是采用类似日志的形式记录下每一次的变更。这样当我们读取的时候，再遍历日志，将相关的变更结果添加到当前的数值上。缺点是，变更很多以及数组很庞大时，效率依然很差。

这个方法超时了。

private int[] sum;
private int[] nums;
private Map<Integer, Integer> log;
public NumArray(int[] nums) {
    this.nums = nums;
    sum = new int[nums.length];
    for(int i = 0 ; i<nums.length ; i++){
        if(i==0) sum[i] = nums[i];
        else sum[i] = sum[i-1] + nums[i];
    }
    
    log = new HashMap<Integer, Integer>();
}

public void update(int i, int val) {
    log.put(i, val - nums[i]);
}

public int sumRange(int i, int j) {
    int origin = 0;
    if(i==0) origin = sum[j];
    else origin = sum[j] - sum[i-1];
    for(Integer key : log.keySet()){
        if(key>=i && key <= j){
            origin += log.get(key);
        }
    }
    return origin;
} 

思路二：Segment Tree

我们将一个数组转化为一棵树，其中当前的数组被均匀的分割并且分别用左子数组和右子数组构建左子树和右子树。最后的叶节点为当前数组的值，非叶结点则记录了子数组的范围以及该子数组中所有元素的和。

举个例子说明一下：
假设当前的数组为[1,2,5]，则构成的Segment Tree为：

    8
   / \
  3   5
 / \
1   2

这里先将[1,2,5]分割为[1,2]和[5]两个子数组，然后分别构造子树。最后的树如上所示。

class SegmentTreeNode{
    int start;
    int end;
    SegmentTreeNode left;
    SegmentTreeNode right;
    int sum;
    
    public SegmentTreeNode(int start, int end){
        this.start = start;
        this.end = end;
    }
}

private SegmentTreeNode buildSegmentTree(int[] nums, int start, int end){
    if(start > end) return null;
    SegmentTreeNode cur = new SegmentTreeNode(start, end);
    if(start == end) cur.sum = nums[start];
    else{
        int mid = (start + end) / 2;
        cur.left = buildSegmentTree(nums, start, mid);
        cur.right = buildSegmentTree(nums, mid+1, end);
        cur.sum = cur.left.sum + cur.right.sum;
    }
    return cur;
}

private SegmentTreeNode root;
public NumArray(int[] nums) {
    this.root = buildSegmentTree(nums, 0, nums.length-1);
}

public void update(int i, int val) {
    update(root, i, val);
}

private void update(SegmentTreeNode root, int position, int val){
    if(root.start == root.end){
        root.sum = val;
    }else{
        int mid = (root.start + root.end) / 2;
        if(position <= mid){
            update(root.left, position, val);
        }else{
            update(root.right, position, val);
        }
        root.sum = root.left.sum + root.right.sum;
    }
}

public int sumRange(int i, int j) {
    return sumRange(root, i, j);
}    

public int sumRange(SegmentTreeNode root, int i, int j){
    if(root.start==i && root.end==j){
        return root.sum;
    }
    int mid = (root.start + root.end )/2;
    if(j<=mid){
        return sumRange(root.left, i, j);
    }else if(i>mid){
        return sumRange(root.right, i, j);
    }else{
        return sumRange(root.left, i, mid) + sumRange(root.right, mid+1, j);
    }
}

要想了解更多关于Segment Tree，请参考这篇文章。

思路三：Binary Indexed Tree

网上有非常多的关于二进制索引数树的教程。它是一个非常轻量级的数据结构，而且几乎就是为这种题目量身打造。可以先从这篇文章和这篇文章了解一下。

class NumArray {
   int[] nums;
    int[] BIT;
    int n;

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

        n = nums.length;
        BIT = new int[n + 1];
        for (int i = 0; i < n; i++)
            init(i, nums[i]);
    }

    //每次更新当前节点的同时更新父节点
    public void init(int i, int val) {
        i++;
        while (i <= n) {
            BIT[i] += val;
            i += (i & -i);
        }
    }

    //更新当前节点，同时将改变传递给父节点
    void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        init(i, diff);
    }

    //
    public int getSum(int i) {
        int sum = 0;
        i++;
        while (i > 0) {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }

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