2D Prefix Sum precomputes the sum from (0,0) to each cell, enabling O(1) submatrix sum queries.
Its core advantage:
Sum of submatrix
(r1,c1)to(r2,c2)in O(1) — inclusion-exclusion over 4 prefix corners.
Focus on recognizing:
“Sum of submatrix” + “Multiple range queries” = 2D Prefix Sum
Core Template
Watch the padded prefix grid fill row by row, then sumRegion(1,1,2,2) resolve as 45 − 6 − 12 + 1 = 28. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
2D Prefix Sum (Submatrix Queries in O(1))
Precompute a padded prefix-sum grid so any axis-aligned submatrix sum is an O(1) four-corner lookup. Essential for fast repeated rectangle queries over a matrix.
Matrix [[1,2,3],[4,5,6],[7,8,9]]. Build the padded prefix grid P (row/col of zeros avoids border checks) with P[i+1][j+1] = P[i][j+1]+P[i+1][j]-P[i][j]+M[i][j]. Then sumRegion(1,1,2,2) = P[3][3] − P[1][3] − P[3][1] + P[1][1] = 45 − 6 − 12 + 1 = 28. The unbuilt cells stay as '·' while the four query corners are highlighted.
1
P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + M[i][j]
2
build every cell, row by row (row 0 of zeros is padding)
3
sumRegion(r1,c1,r2,c2) =
4
P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
5
query sumRegion(1,1,2,2)
class NumMatrix {
int[][] prefix;
public NumMatrix(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
prefix = new int[n + 1][m + 1];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j]
- prefix[i][j] + matrix[i][j];
}
public int sumRegion(int r1, int c1, int r2, int c2) {
return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
- prefix[r2 + 1][c1] + prefix[r1][c1];
}
}class NumMatrix:
def __init__(self, matrix):
n, m = len(matrix), len(matrix[0])
self.prefix = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
self.prefix[i + 1][j + 1] = (
self.prefix[i][j + 1]
+ self.prefix[i + 1][j]
- self.prefix[i][j]
+ matrix[i][j]
)
def sumRegion(self, r1, c1, r2, c2):
return (
self.prefix[r2 + 1][c2 + 1]
- self.prefix[r1][c2 + 1]
- self.prefix[r2 + 1][c1]
+ self.prefix[r1][c1]
)class NumMatrix {
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
prefix.assign(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j]
- prefix[i][j] + matrix[i][j];
}
int sumRegion(int r1, int c1, int r2, int c2) {
return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
- prefix[r2 + 1][c1] + prefix[r1][c1];
}
};class NumMatrix {
constructor(matrix) {
const n = matrix.length,
m = matrix[0].length;
this.prefix = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
for (let i = 0; i < n; i++)
for (let j = 0; j < m; j++)
this.prefix[i + 1][j + 1] =
this.prefix[i][j + 1] +
this.prefix[i + 1][j] -
this.prefix[i][j] +
matrix[i][j];
}
sumRegion(r1, c1, r2, c2) {
return (
this.prefix[r2 + 1][c2 + 1] -
this.prefix[r1][c2 + 1] -
this.prefix[r2 + 1][c1] +
this.prefix[r1][c1]
);
}
}The extra row/column of zeros (
n+1 × m+1) removes every border special-case.
Why Inclusion-Exclusion?
The big box P[r2+1][c2+1] counts everything. To isolate the target:
subtract top strip P[r1][c2+1]
subtract left strip P[r2+1][c1]
add back corner P[r1][c1] (was subtracted twice)Same subtraction trick as 1D — applied once per axis, hence four corners.
Common Mistakes
Formula sign errors.
sum = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1] — memorize the alternating corners.
Skipping the padding row/col.
Without it, every query needs if (r1 > 0) guards — easy to get wrong under time pressure.
Complexity
| Operation | Time |
|---|---|
| Build | O(n·m) |
| Query | O(1) |
Premium Content
Unlock 2D Prefix Sum and all premium lessons with a subscription.
From ₹199.99/year — See plans