213. Range Sum Query 2D - Immutable

Precompute a table where pre[i][j] is the sum of everything above and to the left of (i, j). Any rectangle sum is then four prefix lookups by inclusion-exclusion.

Precompute, then O(1) per query

Build a (m+1) x (n+1) prefix table where pre[i+1][j+1] is the sum of the sub-rectangle from (0,0) to (i,j):

pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j]

Then a query is inclusion-exclusion over four corners:

sumRegion(r1,c1,r2,c2) = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

Worked example

For the sample matrix, sumRegion(2,1,4,3) = 8, sumRegion(1,1,2,2) = 11, sumRegion(1,2,2,4) = 12.

Complexity

• Time: O(m·n) to build, O(1) per query.
• Space: O(m·n).

class NumMatrix {
    private int[][] pre;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = m > 0 ? matrix[0].length : 0;
        pre = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2 + 1][col2 + 1] - pre[row1][col2 + 1]
                - pre[row2 + 1][col1] + pre[row1][col1];
    }
}