What does it solve?
Answer many rectangle-sum queries on a fixed matrix without re-scanning each time. Build a summed-area table P where P[i][j] is the sum of everything in the rectangle from the origin to (i,j).
Key insight: any sub-rectangle sum comes from inclusion-exclusion: take the big block, subtract the strip above, subtract the strip to the left, then add back the corner counted twice. Build is O(R·C), each query is O(1).
The core idea
// build (1-indexed padding)
P[i][j] = grid[i-1][j-1]
+ P[i-1][j] + P[i][j-1] - P[i-1][j-1]
// query rect (r1,c1)-(r2,c2)
sum = P[r2+1][c2+1] - P[r1][c2+1]
- P[r2+1][c1] + P[r1][c1]
P[i][j] = grid[i-1][j-1]
+ P[i-1][j] + P[i][j-1] - P[i-1][j-1]
// query rect (r1,c1)-(r2,c2)
sum = P[r2+1][c2+1] - P[r1][c2+1]
- P[r2+1][c1] + P[r1][c1]
Complexity
Build time
O(R·C)
One pass to fill the summed-area table, each cell computed from three neighbours in O(1).
Query time
O(1)
Every rectangle sum is four table lookups. Space is O(R·C) for the table.
Queries & edge cases
Live animation — inclusion-exclusion on the summed-area table
D: big block (+)
B: top strip (−)
C: left strip (−)
A: corner (+ back)
query rectangle
Original matrix
Summed-area table P (1-indexed)
D = —
B = —
C = —
A = —
Step — of —
D P[r2+1][c2+1]
—
big block
B P[r1][c2+1]
—
subtract top
C P[r2+1][c1]
—
subtract left
Rectangle sum
—
D − B − C + A
Select a query and press Play to start.
✓ Sum: —
Speed
Medium
Step-by-step table
| Step | Phase | Term | Cell | Value | Running |
|---|
C++ implementation
prefix_2d.cpp
#include <bits/stdc++.h> using namespace std; struct Matrix2D { vector<vector<int>> P; // (R+1) x (C+1), 1-indexed Matrix2D(vector<vector<int>>& g) { int R = g.size(), C = g[0].size(); P.assign(R + 1, vector<int>(C + 1, 0)); for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) P[i][j] = g[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]; } // sum of rectangle (r1,c1) .. (r2,c2) inclusive, 0-indexed int query(int r1, int c1, int r2, int c2) { return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]; } }; int main() { vector<vector<int>> g = {{3,0,1,4},{5,6,3,2},{1,2,0,1},{4,1,0,5}}; Matrix2D m(g); cout << m.query(1,1,2,2) << "\n"; // 11 return 0; }
My Notes