308. Range Sum Query 2D - Mutable

Version #1 2D Fenwick Tree

77.62 %
class NumMatrix {

    int[][] tree;
    int rows, cols;
    int[][] matrix;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        this.matrix = matrix;
        rows = matrix.length;
        cols = matrix[0].length;
        tree = new int[rows + 1][cols + 1]; // 1 indexed
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                updateTree(i, j, matrix[i][j]);
            }
        }
    }
   
    public void update(int row, int col, int val) {
        if (rows == 0 || cols == 0) return;
        updateTree(row, col, val - matrix[row][col]);
        matrix[row][col] = val;
    }
   
    private void updateTree(int row, int col, int diff) {
        for (int i = row + 1; i <= rows; i += (i & (-i))) {
            for (int j = col + 1; j <= cols; j += (j & (-j))) {
                tree[i][j] += diff;
            }
        }
    }
   
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (rows == 0 || cols == 0) return 0;
        // (row2, col1)       (row2, col2)
        // (row1, col1)       (row1, col2)
        return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
    }
   
    private int sum(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= (i & (-i))) {
            for (int j = col + 1; j > 0; j -= (j & (-j))) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
}