Range Sum Query 2D Immutable

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).

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.

Solution:

public class NumMatrix {
    
    int[][] BIT;

    public void insert(int[][] mat, int i, int j){
        int idx = i + 1;
        while(idx<BIT.length){
            int idy = j + 1;
            while(idy<BIT[0].length){
                BIT[idx][idy] += mat[i][j];
                idy += (idy&-idy);
            }
            idx += (idx&-idx);
        }
    }
    
    public NumMatrix(int[][] matrix) {
        if(matrix.length==0) return;
        BIT = 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++){
                insert(matrix, i, j);
            }
        }
    }
    
    public int getSum(int i, int j){
        int sum = 0;
        int idx = i + 1;
        while(idx>0){
            int idy = j + 1;
            while(idy>0){
                sum += BIT[idx][idy];
                idy -= (idy&-idy);
            }
            idx -= (idx&-idx);
        }
        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 numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);