摘要：表現在二進制上的規律每次加上最末尾的求末尾的就拿這個數和它的補碼于。還有要求不是，要轉換一下，和之前那道的思路差不多。這里用一個的表示從到的和。

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example: Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1 
sumRange(2, 5) -> -1  
sumRange(0, 5) -3
Note:
You may assume that the array does not change. 
There are many calls to sumRange function.

用dp解。dp[i]表示sumRange(0, i-1)
function是dp[i+1] = dp[i] + nums[i]
所以sumRange(i, j) = dp[j+1] - dp[i]

public class NumArray {
    int[] dp;
    public NumArray(int[] nums) {
        dp = new int[nums.length + 1];
        for(int i = 0; i < nums.length; i++) {
            dp[i+1] = dp[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return dp[j + 1] - dp[i];
    }
}

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.

和上一題的區別在于，這次數組里面的值會動態的變化，所以不能和上面一題一樣，最開始初始化一個dp數組之后就不管了。如果還是用dp數組，那么每次update之后都得重新再改一遍，O(N)時間復雜度太高。
用binary index tree來做，update和sum的時間復雜度都是O(NlogN)。原理如下：
index: 1------2------3------4------5------6------7-----8-----9
binary: 0001-0010-0011-0100-0101-0110-0111-1000-1001
value: 2------5------6------3------1------7------5-----3-----2

tree[i]: [1,1]--[1,2]--[3,3]--[1,4]--[5,5]--[5,6]--[7,7]--[1,8]--[9,9]

Level1: 2------7------------16------------------------34

Level2: --------------6-------------1-----8-------------------9

right index in level1 has one "1" in binary representation.
right index in level2 has two "1" in binary representation.
......

2個主要的method：add 和 sum
add(idx, val): add val to nums[i]
sum(idx): get the sum from 1 to idx

add的時候改怎么操作呢？
舉個例子，比如add(5, 2)， 我想在index = 5的地方加2，那么：

start從idx = 5開始，tree[5] += 2

接著，要更新tree[6]，也就是sum(5, 6)

再接著更新tree[8]，也就是sum(1, 8)

在圖里的表現就是我先從start開始，把start同一level所有往右相鄰的更新一遍，沒有相鄰的之后，就往上一面一層走，重復更新的過程。直到idx超過長度。

表現在二進制上的規律：

5 -------> 6 ------> 8

0101 -> 0110 -> 1000

每次加上最末尾的‘1’

0101 + 0001 = 0110

0110 + 0010 = 1000

求末尾的‘1’就拿這個數和它的補碼于。
假設這個數是x = n(1,0)-1-m(0)
m(0)表示這個數末尾有m個0，n(1,0)表示這個數前面有n個1或者0。那么第一個1就出現在從右數第m+1位上。

現在求x的反碼，~x = ~n(1,0)-0-m(1)

那么x的補碼就是：-x = ~n(1,0)-1-m(0)

所以: x&-x = n(0)-1-m(0)

void add(int idx, int val) {
    while(idx < tree.length) {
        tree[idx] += val;
        idx += i & -i;
    }
}

int sum(int idx) {
    int result = 0;
    while(idx > 0) {
        result += tree[idx];
        idx += i & -i;
    }
    return result;
}

sum的方法同理，init的直接用add即可。這道題注意下數組的index是從0開始，所以每次要+1。還有要求update不是add，要轉換一下，update(idx, val) = add(idx, val - nums[idx])

public class NumArray {
    // binary index tree
    int[] tree;
    int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
        tree = new int[nums.length + 1];
        for(int i = 0; i < nums.length; i++) {
            add(i, nums[i]);
        }
    }
    
    private void add(int i, int val) {
        i += 1;
        while(i < tree.length) {
            tree[i] += val;
            i += i & -i;
        }
    }
    
    public void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        add(i, diff);
    }
    
    public int sumRange(int i, int j) {
        return sum(j) - sum(i - 1);
    }
    
    // return the sumRange(0, i)
    private int sum(int i) {
        i+= 1;
        int result = 0;
        while(i > 0) {
            result += tree[i];
            i -= i & -i;
        }
        return result;
    }
}

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example: 
Given matrix = [
[3, 0, 1, 4, 2],   
[5, 6, 3, 2, 1],   
[1, 2, 0, 1, 5],   
[4, 1, 0, 1, 7],   
[1, 0, 3, 0, 5] ]
sumRegion(2, 1, 4, 3) -> 8 
sumRegion(1, 1, 2, 2) -> 11 
sumRegion(1, 2, 2, 4) -> 12 
Note: 
You may assume that the matrix does not change.
There are many calls to sumRegion function. You may assume that row1 ≤ row2 and col1 ≤ col2.

和之前那道1d的思路差不多。這里用一個2d的prefix array:
dp[i + 1] [j + 1] 表示從 [0, 0] 到 [i, j] 的和。function是：
dp[i + 1] [j + 1] = dp[i + 1] [j] + dp[i] [j + 1] - dp[i] [j] + matrix[i] [j]
所以sum(row1, col1, row2, col2) = dp[row2 + 1] [col2 + 1] - dp[row1] [col2 + 1] - dp[row2 + 1] [col1] + dp[row1] [col1]

public class NumMatrix {
    // dp
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        dp = new int[matrix.length + 1][matrix[0].length + 1];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10
Note:

The matrix is only modifiable by the update function.

You may assume the number of calls to update and sumRegion function is distributed evenly.

You may assume that row1 ≤ row2 and col1 ≤ col2.

和1d的mutable的差不多。還是用binary index tree來做。時間還是都是O(NlogN)。