We're given a 2D grid of integers and need to answer rectangle sum queries efficiently. Each query hands us the top-left and bottom-right corners of a rectangle, and we need to return the sum of all elements inside it.

A single query is easy: loop through the rectangle and add everything up. The difficulty is that sumRegion can be called up to 10,000 times, and the problem requires O(1) per query. That rules out re-scanning the rectangle each time and forces us to do preprocessing during construction that lets any later query resolve in constant time.

The 1D version of this problem (Range Sum Query - Immutable) is solved with a prefix sum array, where one subtraction gives the sum of any subarray in O(1). The question is whether that idea extends to two dimensions.

Key Constraints:

Intuition

Do exactly what the problem describes: for each query, iterate through every cell in the rectangle and add up the values. The constructor stores the matrix and does no preprocessing.

This is correct but slow on many queries over a large matrix. Each query takes O(m * n) in the worst case (a rectangle spanning the entire matrix), and with up to 10,000 queries that work is repeated from scratch every time even though the matrix never changes.

Algorithm

Visualization and Code

The next approach precomputes row-wise prefix sums so each row's contribution to a query becomes a single subtraction instead of a scan.

Intuition

Compute prefix sums for each row independently. With a per-row prefix array, the sum of any segment within a row is one subtraction. A rectangle query then loops only over the rows from row1 to row2, taking each row's contribution in O(1) instead of scanning that row's columns.

This brings the per-query cost from O(m * n) down to O(m), and it is the direct one-dimensional version of the two-dimensional prefix sum in the next approach.

For each row i, build a prefix array where rowPrefix[i][j] = sum of matrix[i][0..j-1]. The sum of row i from column col1 to col2 is rowPrefix[i][col2 + 1] - rowPrefix[i][col1]. The leading zero at rowPrefix[i][0] is what lets col1 = 0 work without a special case.

Algorithm

Visualization and Code

Row prefixes still require a loop over up to m rows per query. The next approach precomputes sums in both dimensions at once, reducing every query to a fixed number of lookups regardless of rectangle size.

Intuition

The 2D prefix sum precomputes one value per cell and answers every query in constant time using inclusion-exclusion.

Define a prefix sum matrix where prefix[i][j] stores the sum of all elements in the rectangle from (0, 0) to (i-1, j-1). Each entry is the sum of one full corner-anchored rectangle. Any arbitrary rectangle sum can then be expressed as a combination of four such corner rectangles.

To get the sum of the rectangle from (row1, col1) to (row2, col2), start with prefix[row2+1][col2+1], the sum of everything from the origin to the bottom-right corner. That overcounts: it includes the band above the target rectangle and the band to its left. Subtract both:

The two bands overlap in the top-left corner region, so that corner has now been subtracted twice. Add it back once:

What remains is exactly the target rectangle: four lookups and three arithmetic operations per query.

Algorithm

Visualization and Code