265/670

265. Range Sum Query 2D - Immutable

Medium

Design a class NumMatrix around a fixed grid of integers matrix that can answer many rectangle-sum questions quickly.

The constructor receives matrix, a grid with rows rows and cols columns. The grid never changes after construction.
sum_region(row1, col1, row2, col2) returns the sum of every element inside the axis-aligned rectangle whose top-left corner is (row1, col1) and whose bottom-right corner is (row2, col2), all four edges included.

The same grid is queried many times, so precompute in the constructor and make each query constant time.

Example 1: sum_region(1, 1, 2, 2)sum_region(1, 1, 2, 2) covers the four highlighted cells, inclusive of all four edges: 6 + 7 + 10 + 11 = 34.

Example 1:

Input: NumMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]); sum_region(1,1,2,2), sum_region(0,0,3,3), sum_region(2,0,2,3)

Output: [34, 136, 42]

Explanation: The first rectangle covers 6 + 7 + 10 + 11 = 34 (shown in the figure). The second is the whole grid, 136. The third is all of row 2: 9 + 10 + 11 + 12 = 42.

Example 2:

Input: NumMatrix([[-4]]); sum_region(0, 0, 0, 0)

Output: [-4]

Explanation: A 1×1 grid: the only rectangle is the single cell itself.

Constraints:

1 ≤ rows, cols ≤ 200
-10⁴ ≤ matrix[r][c] ≤ 10⁴
0 ≤ row1 ≤ row2 < rows and 0 ≤ col1 ≤ col2 < cols
At most 10⁴ calls to sum_region

Hints:

The 1D version of this problem is solved with prefix sums: prefix[i] holds the sum of the first i elements, and any range is one subtraction. What is the 2D analogue of "everything before this point"?

Let P[r][c] be the sum of the whole sub-grid above and to the left of cell (r, c) — rows 0..r-1, columns 0..c-1, with a padded zero row and column. Build it in one sweep: P[r+1][c+1] = matrix[r][c] + P[r][c+1] + P[r+1][c] - P[r][c].

A query is then four lookups: take the big rectangle through (row2, col2), cut away the strip above row1 and the strip left of col1, and add back their overlapping corner, which was removed twice.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: NumMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]); sum_region(1,1,2,2), sum_region(0,0,3,3), sum_region(2,0,2,3)

Expected output: [34, 136, 42]