15ms Very Concise Java Code Using BIT


  • 9
    O

    Salute to https://leetcode.com/discuss/71169/java-2d-binary-indexed-tree-solution-clean-and-short-17ms

    public class NumMatrix {
        // Using 2D Binary Indexed Tree, 2D BIT Def:
        // bit[i][j] saves the rangeSum of [i-(i&-i), i] x [j-(j&-j), j]
        // note bit index == matrix index + 1
        int n, m;
        int[][] bit, a;
    
        public NumMatrix(int[][] matrix) {
            if (matrix.length < 1) return;
            n = matrix.length; m = matrix[0].length;
            bit = new int[n + 1][m + 1]; a = new int[n][m];
            
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    update(i, j, matrix[i][j]);
        }
    
        public void update(int row, int col, int val) {
            int diff = val - a[row][col];
            a[row][col] = val;
            for (int i = row + 1; i <= n; i += i & -i)
                for (int j = col + 1; j <= m; j += j & -j)
                    bit[i][j] += diff;
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
        }
        
        public int sum(int row, int col) {
            int tot = 0;
            for (int i = row + 1; i > 0; i -= i & -i)
                for (int j = col + 1; j > 0; j -= j & -j)
                    tot += bit[i][j];
            return tot;
        }
    }

Log in to reply
 

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