solution in java with Fenwich Tree


  • 0
    M

    public class NumMatrix {
    //http://www.hawstein.com/posts/binary-indexed-trees.html
    // Fenwick Tree
    int[][] Bit;
    int[][] matrix;

    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length==0) return;
        int row = matrix.length;
        int col = matrix[0].length;
        Bit = new int[row+1][col+1];
        this.matrix = new int[row][col];
        for(int i  = 0; i < row; i++) {
            for(int j  = 0; j < col; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }
    
    public void update(int row, int col, int val) {
        int addi = val - matrix[row][col];
        matrix[row][col] = val;
        // update fenwich tree data
        for(int i = row + 1; i < Bit.length; i+= i&(-i)) {
            for(int j = col + 1; j < Bit[0].length; j+= j&(-j)) {
                Bit[i][j] += addi;
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return getSum(row2+1, col2+1) - getSum(row1, col2+1) - getSum(row2 + 1, col1) + getSum(row1, col1);
    }
    
    public int getSum(int x, int y) {
        int sum = 0;
        for(int i = x; i > 0; i-=i&(-i)) {
            for(int j = y; j > 0; j-=j&(-j)) {
                sum += Bit[i][j];
            }
        }
        return sum;
    }
    

    }


Log in to reply
 

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