34. Range Sum Query 2D — Immutable
Construct an immutable view of the matrix that can answer sums over rectangular regions. Each query includes its starting row and column and excludes its ending row and column.
The captured values must not change if the caller later mutates the input. Be precise about the four boundaries and about empty query rectangles.
Example 1
Input
matrix=[[1,2,3],[4,5,6]]; sumRegion(0,1,2,3)
Output
16
Explanation: Rows 0 and 1, columns 1 and 2 contribute 2+3+5+6.
Example 2
Input
matrix=[[1,-2],[3,4]]; sumRegion(1,0,2,2)
Output
7
Explanation: The half-open second-row rectangle contains 3 and 4.
Constraints
0 <= rows, columns <= 300-231 <= matrix[r][c] <= 231 - 10 <= r1 <= r2 <= rows0 <= c1 <= c2 <= columns- Queries cover the half-open rectangle [r1, r2) × [c1, c2).
Hints
Hint 1
What does the sum at boundary (r,c) include?
Hint 2
Two removed strips overlap; how often was that overlap subtracted?
Hint 3
Use a padded table and big-above-left+overlap for both construction and queries.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Build a padded table and query interior and empty areas
[[1,2,3],[4,-5,6],[7,8,9]]
[[1,1,3,3],[0,0,3,3],[1,2,1,3]]
[18,35,0]