Range Sum Query 2D – Immutable

也是2d fenwick树.

class NumMatrix {
int[][] matrix;
    int[][] BIT;
    int n;
    int m;
      public int lowbit(int x){
        return x & (-x);
    }
    
    public void set(int r, int c, int val){
        r++;
        c++;
       for(int i = r; i <= n; i += lowbit(i)){
            for(int j = c; j <= m; j += lowbit(j)){
                BIT[i][j] += val;
            }
        }
    }
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.n = matrix.length;
        this.m = matrix[0].length;
        this.BIT = new int[n + 1][m + 1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                set(i,j,matrix[i][j]);
            }
        }
    }
       public int sum(int r, int c) {
        int s = 0;
        r++;
        c++;
        for(int i = r; i > 0; i -= lowbit(i)){
            for(int j = c; j > 0; j -= lowbit(j)){
                s += BIT[i][j];
            }
        }
        return s;
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return (sum(row2, col2) + sum(row1 - 1, col1 - 1)) - (sum(row2, col1 - 1) + sum(row1 - 1, col2));
    }
}

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