Range Sum Query 2D - Mutable

Question

Given a 2D matrix, find the sum of the elements inside the rectangle defined by (row1, col1), (row2, col2).

Analysis

Same as the sub-Sum approach, this method uses another data structure which averages the time complexity of Search and Update query both to O(lgn).

        ___________________
        |       |          |
        |       |          |
        |______a|_________b|
        |       |          |
        |       |          |
        |       |    S     |
        |       |          |
        |______c|_________d|

        S=sum(d)+sum(a)-sum(b)-sum(c)

Refer to the Binary Indexed Tree tutorial

Solution

public class NumMatrix {

    int[][] tree;
    int[][] nums;
    int m;
    int n;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        tree = new int[m+1][n+1];
        nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        int delta = val - nums[row][col];
        nums[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] += delta;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        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 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;
    }
}