2D Binary Indexed Tree solution


  • 0
    A
    public class NumMatrix {
    
        int[][] BIT;
        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;
            BIT = new int[m+1][n+1];
            nums = matrix;
                     
            //BIT creation
            createBIT(matrix);
        }
        
        public void update(int row, int col, int val) {
            int delta = val - nums[row] [col];
            nums[row][col] = val;
            updateBIT(delta, row+1, col+1);
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            int iMin = Math.min(row1, row2);
            int iMax = Math.max(row1, row2);
            int jMin = Math.min(col1, col2);
            int jMax = Math.max(col1, col2);
            
            //bottom right corner - top right corner - bottom left corner + common left top corner
            sum = getSum(iMax, jMax) - getSum(iMin-1,jMax) - getSum(iMax, jMin-1) + getSum(iMin-1, jMin-1); 
            return sum;
        }
        
        private void createBIT(int[][] matrix){
            for(int i = 1;i <= m;i++){
                for(int j = 1;j <= n; j++){
                    updateBIT(matrix[i-1][j-1], i, j);
                }
            }
        }
        
        private void updateBIT(int val, int row, int col){
            
            for(int i = row; i< BIT.length; i = getNext(i)){
                for(int j = col; j< BIT[0].length ;j = getNext(j)){
                    BIT[i][j] += val;
                }
            }
        }
        
        private int getSum(int row, int col){
            int sum = 0;
            row++; //index are always starting from 1...BIT.length
            col++;
            
            for(int i=row;i>0;i = getParent(i)){
                for(int j = col; j>0;j=getParent(j)){
                    sum += BIT[i][j];
                }
            }
            
            return sum;
        }
        
        private int getParent(int index){
            return index - (index & -index);
        }
        
         private int getNext(int index){
            return index + (index & -index);
        }
    }
    
    /**
     * 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);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.