My Java BIT Solution, 100%


  • 2
    S
    public class NumMatrix {
        // Binary Indexed Tree
        int[][] tree;
        int[][] sums;
        int[][] matrix;
        int m, n;
        public NumMatrix(int[][] matrix) {
            if (matrix.length == 0) {
                return;
            }
            this.m = matrix.length;
            this.n = matrix[0].length;
            this.tree = new int[m + 1][n + 1];
            this.sums = new int[m + 1][n + 1];
            this.matrix = matrix;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    int r = i - (i & -i);
                    int c = j - (j & -j);
                    tree[i][j] = sums[i][j] - sums[r][j] - sums[i][c] + sums[r][c];
                }
            }
        }
    
        public void update(int row, int col, int val) {
            int diff = val - matrix[row][col];
            matrix[row][col] = val;
            for (int i = row + 1; i <= m; i += (i & -i)) {
                for (int j = col + 1; j <= n; j += (j & -j)) {
                    tree[i][j] += diff;
                }
            }
        }
    
        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 row, int col) {
            int sum = 0;
            for (int i = row; i > 0; i -= (i & -i)) {
                for (int j = col; j > 0; j -= (j & -j)) {
                    sum += tree[i][j];
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

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