BiruLyu
5/22/2017 - 5:47 AM

308. Range Sum Query 2D - Mutable.java

public class NumMatrix {
    private int[][] nums;
    private int[][] BITree;
    private int m;
    private int n;
    
    public NumMatrix(int[][] matrix) {
        
        //if (matrix==null||matrix.length == 0 || matrix[0].length == 0) return;//["NumMatrix"] [[[]]]
         if (matrix==null||matrix.length == 0) return;
        this.m = matrix.length;// row num
        this.n = matrix[0].length;
        this.nums = new int[this.m][this.n];
        this.BITree = new int[this.m + 1][this.n + 1];
        
        for (int i = 0; i < this.m; i++){
            for (int j = 0; j < this.n; j++){
                update(i, j, matrix[i][j]);
            }
        }
        
    }
    
    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        //if (this.m == 0 || this.n == 0) return; //["NumMatrix"] [[[]]]
        int diff = val - nums[row][col];
        nums[row][col] = val;

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

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */