My code:

public class NumMatrix {
    int[][] matrix;
    int[][] BIT;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        this.matrix = matrix;
        BIT = new int[matrix.length][matrix[0].length + 1];
        for (int i = 0; i < BIT.length; i++) {
            for (int j = 1; j < BIT[0].length; j++) {
                updateBIT(i, j - 1, matrix[i][j - 1]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (this.BIT == null) {
            return;
        }
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        updateBIT(row, col, diff);
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (BIT == null) {
            return -1;
        }
        if (col1 == 0) {
            int sum = 0;
            for (int i = row1; i <= row2; i++) {
                sum += getSum(i, col2);
            }
            return sum;
        }
        else {
            int sum = 0;
            for (int i = row1; i <= row2; i++) {
                sum += getSum(i, col2) - getSum(i, col1 - 1);
            }
            return sum;
        }
    }
    
    private void updateBIT(int row, int col, int diff) {
        int index = col + 1;
        while (index < BIT[0].length) {
            BIT[row][index] += diff;
            index += (index & -index);
        }
    }
    
    private int getSum(int row, int col) {
        int index = col + 1;
        int ans = 0;
        while (index > 0) {
            ans += BIT[row][index];
            index -= (index & -index);
        }
        
        return ans;
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.update(1, 1, 10);
// numMatrix.sumRegion(1, 2, 3, 4);

這是我自己寫出來(lái)的徐紧。
把 2dmatrix的每一行當(dāng)成獨(dú)立的BIT，然后，來(lái)求暇矫。
構(gòu)建 2d BIT的時(shí)間復(fù)雜度是：O(MN log N)
sum: O(M log N)
update: O(M log N)

然后看了答案的一種寫法，一種沒徹底搞清楚是什么原理择吊，只能意會(huì)李根。

My code:

public class NumMatrix {

    int[][] tree;
    int[][] nums;
    int m;
    int n;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        tree = new int[m+1][n+1];
        nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for (int i = row + 1; i <= m; i += i & (-i)) {
            for (int j = col + 1; j <= n; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
    }
    
    public int sum(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & (-i)) {
            for (int j = col; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
}

reference:
https://discuss.leetcode.com/topic/30343/java-2d-binary-indexed-tree-solution-clean-and-short-17ms/2

http://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/

Time Complexity:
Both updateBIT(x, y, val) function and getSum(x, y) function takes O(log(NM)) time.
Building the 2D BIT takes O(NM log(NM)).
Since in each of the queries we are calling getSum(x, y) function so answering all the Q queries takesO(Q.log(NM)) time.

Hence the overall time complexity of the program is O((NM+Q).log(NM)) where,N = maximum X co-ordinate of the whole matrix.M = maximum Y co-ordinate of the whole matrix.Q = Number of queries.
**Auxiliary Space: **O(NM) to store the BIT and the auxiliary array

Anyway, Good luck, Richardo! -- 09/04/2016