Range Sum Query - Mutable

题目地址：
https://leetcode.com/problems/range-sum-query-mutable/description/

题目：

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

解题思路：
这道题可以用辅助的array来做，记录从当前节点到之前所有元素的和。但是会TLE。

代码：

private int[] sums;
private int[] input;

public NumArray(int[] nums) {
    sums = new int[nums.length];
    input = new int[nums.length];
    int prev = 0;
    for(int i = 0; i <= nums.length - 1; i++){
        input[i] = nums[i];
        sums[i] = prev + nums[i];
        prev = sums[i];
    }
}

public void update(int i, int val) {
    int diff = val - input[i];
    input[i] = val;
    while(i <= input.length - 1){
        sums[i] += diff;
        i++;
    }
}

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

we could use SegmentTree(线段树) to do this: time: O(log(n)), space: O(n):
I got the idea from this page:
http://blog.csdn.net/xing1989/article/details/9464677

My code revised from this page:
http://algs4.cs.princeton.edu/99misc/SegmentTree.java.html

// good stuff: also use O(n) space , but time complexity is O(lgn)    private Node[] heap;
    private int[] array;
    private int size;
    // build a map to store the index if the array and the index in the heap.    private Map<Integer, Integer> map;

    class Node{
        int from;
        int to;
        int sum;
    }

    public NumArray(int[] nums) {
        this.array = Arrays.copyOf(nums, nums.length);
        map = new HashMap<>();
        //The max size of this array is about 2 * 2 ^ log2(n) - 1        size = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) nums.length) / Math.log(2.0)) + 1)));
        heap = new Node[size];
        build(0, 0, array.length);
    }

    private void build(int index, int from, int size) {
        if(size == 0){
            return;
        }
        heap[index] = new Node();
        heap[index].from = from;
        heap[index].to = from + size - 1;
        if(size == 1){
            heap[index].sum = array[from];
            map.put(from, index);
        }
        else{
            // build the left heap            build(index * 2 + 1, from, size - size / 2);
            // build the right heap            build(index * 2 + 2, from + size - size / 2, size / 2);
            // left child index: 2 * index + 1   , right child index: 2 * index + 2            heap[index].sum = heap[index * 2 + 1].sum + heap[index * 2 + 2].sum;
        }
    }

    public void update(int i, int val) {
        int currIndex = map.get(i);
        heap[currIndex].sum = val;
        int parentIndex = (currIndex - 1) / 2;
        while(currIndex != 0){
            int theOtherChildIndex = parentIndex * 2 + 1 == currIndex ? parentIndex * 2 + 2 : parentIndex * 2 + 1;
            heap[parentIndex].sum = heap[currIndex].sum + heap[theOtherChildIndex].sum;
            currIndex = parentIndex;
            parentIndex = (currIndex - 1) / 2;
        }
    }

    public int sumRange(int i, int j) {
        int rst = query(0, i, j);
        return rst;
    }

    private int query(int curr, int from, int to) {
        Node node = heap[curr];
        if(node == null){
            return 0;
        }
        if(isRange(from, to ,node)){
            return node.sum;
        }
        else if (contains(from, to, node)) {
            Node left = heap[curr * 2 + 1];
            Node right = heap[curr * 2 + 2];
            int rst = 0;
            if(left != null){
                rst += left.to >= from ? query(curr * 2 + 1, from, Math.min(left.to, to)) : 0;
            }
            if(right != null){
                rst += to >= right.from ? query(curr * 2 + 2, Math.max(right.from, from), to) : 0;
            }
            return rst;
        }
        else{
            return 0;
        }
    }

    private boolean isRange(int from, int to, Node node) {
        return node.from == from && node.to == to;
    }

    private boolean contains(int from, int to, Node node) {
        return node.from <= from && node.to >= to;
    }

    public static void main(String[] args){
//        int[] nums = {1, 3, 5, 7, 9, 11};        int[] nums = {0, 9, 5, 7, 3};
        NumArray numArray = new NumArray(nums);
//        numArray.printHeap(numArray.heap);        int rst = numArray.sumRange(4, 4);
        System.out.println(rst);
//        numArray.update(3, 8);//        rst = numArray.sumRange(0, 5);//        System.out.println(rst);    }

    private void printHeap(Node[] nums){
        for(int i = 0; i <= nums.length - 1; i++){
            if(nums[i] != null){
                System.out.print(nums[i].sum);
                if(i != nums.length - 1){
                    System.out.print("->");
                }
            }
        }
    }

这道题还有一个Follow up，就是当输入是2D数组的时候。这个时候如果是segmentTree的话，heap是一个四叉树。或者也可以建一个一维度的segment tree。