摘要：表現(xiàn)在二進(jìn)制上的規(guī)律每次加上最末尾的求末尾的就拿這個(gè)數(shù)和它的補(bǔ)碼于。還有要求不是，要轉(zhuǎn)換一下，和之前那道的思路差不多。這里用一個(gè)的表示從到的和。

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.

和上一題的區(qū)別在于，這次數(shù)組里面的值會(huì)動(dòng)態(tài)的變化，所以不能和上面一題一樣，最開始初始化一個(gè)dp數(shù)組之后就不管了。如果還是用dp數(shù)組，那么每次update之后都得重新再改一遍，O(N)時(shí)間復(fù)雜度太高。
用binary index tree來做，update和sum的時(shí)間復(fù)雜度都是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個(gè)主要的method：add 和 sum
add(idx, val): add val to nums[i]
sum(idx): get the sum from 1 to idx

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

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

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

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

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

表現(xiàn)在二進(jìn)制上的規(guī)律：

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

0101 -> 0110 -> 1000

每次加上最末尾的‘1’

0101 + 0001 = 0110

0110 + 0010 = 1000

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

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

那么x的補(bǔ)碼就是：-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即可。這道題注意下數(shù)組的index是從0開始，所以每次要+1。還有要求update不是add，要轉(zhuǎn)換一下，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的思路差不多。這里用一個(gè)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來做。時(shí)間還是都是O(NlogN)。