share two of my solution using Java(segment tree and BIT)!


  • 0
    C

    The first is to use segment tree:

    public class NumMatrix {
        int[][] treenodes;
        int collen;
        int rowlen;
        public NumMatrix(int[][] matrix) {
            if(matrix==null||matrix.length<1) return;
            rowlen=matrix.length;
            collen=matrix[0].length;
            treenodes=new int[rowlen][collen*2];
            for(int i=0;i<rowlen;i++){
                for(int j=0;j<collen;j++){
                    treenodes[i][collen+j]=matrix[i][j];
                }
                for(int j=collen-1;j>=0;j--){
                    treenodes[i][j]=treenodes[i][j<<1]+treenodes[i][(j<<1)|1];
                }
            }
        }
        
        public void update(int row, int col, int val) {
              int j=col+collen;
              int dif=val-treenodes[row][j];
              while(j>0){
                  treenodes[row][j]+=dif;
                  j>>=1;
              }
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
             int sum=0;
             for(int row=row1;row<=row2;row++){
                 int i=col1+collen;
                 int j=col2+collen;
                 for(;i<=j;i>>=1,j>>=1){
                     if((i&1)==1){
                         sum+=treenodes[row][i];
                         i++;
                     }
                     if((j&1)==0){
                         sum+=treenodes[row][j];
                         j--;
                     }
                 }
             }
             return sum;
        }
    }
    

    The second is to use binary indexed tree which can improve the efficiency:

    
    public class NumMatrix {
        int[][] treenodes;
        int[][] nums;
        int collen;
        int rowlen;
        
        public NumMatrix(int[][] matrix) {
            if(matrix==null||matrix.length<1) return;
            
             this.rowlen=matrix.length;
             this.collen=matrix[0].length;
             this.nums=new int[rowlen][collen];
             
             treenodes=new int[rowlen+1][collen+1];
             for(int i=0;i<rowlen;i++){
                 for(int j=0;j<collen;j++){
                     update(i,j,matrix[i][j]);
                 }
             }
        }
        
        public void update(int row, int col, int val) {
              int i=row+1;
              int j=col+1;
              
              int dif=val-nums[row][col];
              this.nums[row][col]=val;
              while(i<=rowlen){
                  j=col+1;
                 while(j<=collen){
                     treenodes[i][j]+=dif;
                     j+=(j&(-j));
                 }
                 i+=(i&(-i)); 
              }
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
              return upperleftsum(row2,col2)+upperleftsum(row1-1,col1-1)-upperleftsum(row1-1,col2)-upperleftsum(row2,col1-1);
        }
        
        public int upperleftsum(int row,int col){
            if(col<0) return 0;
            if(row<0) return 0;
            int i=row+1;
            int j=col+1;
            int sum=0;
            while(i>0){
                j=col+1;
                while(j>0){
                    sum+=treenodes[i][j];
                    j-=(j&(-j));
                }
                i-=(i&(-i));
            }
            return sum;
        }
    }
    
    

Log in to reply
 

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