Problem Statement
Range Sum Query 2D - Immutable
You are given a grid of numbers (a 2D matrix). People will ask you many times: "What is the total of all the numbers inside this rectangle?" The rectangle is given by a top-left corner (row1, col1) and a bottom-right corner (row2, col2). The grid never changes, so we want a way to answer each question fast, even if there are thousands of questions. The trick is a prefix sum, which is a number you compute ahead of time that already holds a running total, so you do not have to add things up over and over.
Signals to notice
Brute force first
Sum rectangle each query — O(mn).
The key insight
2D prefix sums. Query = inclusion-exclusion on 4 corners. O(mn) precompute, O(1) per query.
Trace it on matrix=[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]], query sumRegion(2,1,4,3)
Build prefix (size 6x6, all 0 in row 0 / col 0). Fill p[i][j]=matrix[i-1][j-1]+p[i-1][j]+p[i][j-1]-p[i-1][j-1]. Row1 prefix over [3,0,1,4,2] -> p[1]=[0,3,3,4,8,10]. Row2 adds [5,6,3,2,1] -> p[2]=[0,8,14,18,24,27]. Row3 adds [1,2,0,1,5] -> p[3]=[0,9,17,21,28,36]. Row4 adds [4,1,0,1,7] -> p[4]=[0,13,22,26,34,49]. Row5 adds [1,0,3,0,5] -> p[5]=[0,14,23,30,38,58]. Query sumRegion(2,1,4,3): p[r2+1][c2+1]-p[r1][c2+1]-p[r2+1][c1]+p[r1][c1] = p[5][4]-p[2][4]-p[5][1]+p[2][1] = 38-24-14+8 = 8. Return 8.
What must stay true
prefix[i][j] stores sum of rectangle (0,0)→(i-1,j-1). Sub-rectangle via 4 corners: add and subtract.
Shape of the loop
build p[m+1][n+1] filled with 0 # padded prefix grid
for i in 1..m, for j in 1..n:
p[i][j] = M[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
sumRegion(r1,c1,r2,c2):
return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Getting the formula wrong — draw the 4 rectangles to visualize.