PrefixPrefix Techniques
2D Prefix Sum
Precompute P[i][j] = sum of the rectangle from (0,0) to (i-1,j-1) so any submatrix sum is four lookups via inclusion–exclusion.
0
0
0
0
0
0
0
0
0
Input matrix a
| c0 | c1 | c2 | c3 |
|---|---|---|---|
| 3 | 0 | 1 | 4 |
| 5 | 6 | 3 | 2 |
| 1 | 2 | 0 | 1 |
| 4 | 1 | 0 | 1 |
1/19Build a (R+1)×(C+1) prefix table where P[r][c] is the sum of the top-left r×c block of a. Row 0 and column 0 are zeros so borders need no special cases.
Cell being computedAdded (up / left)Subtracted (diagonal)Queried submatrixAnswer
PseudocodeLearn 2D Prefix Sum →
1P = (R+1) × (C+1) zeros2for r in 1..R, c in 1..C:3 P[r][c] = a[r-1][c-1] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]4sum(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]Variables
R4
C4
Complexity
best O(R·C)
avg O(R·C + q)
worst O(R·C + q)
space O(R·C)
Speed