Intermediate · Module 8 · Lesson 2
2D prefix sums
Answer rectangular matrix queries.
15–25 min readLesson 43 of 123
Lesson 43 of 123
1d streakTheory lesson · Step-by-step
Understand 2D prefix sums
Answer rectangular matrix queries.
Worked approach
Trace the reasoning step by step
- 1Build cumulative rows and columns.
- 2Correct the double-counted overlap.
- 3For a query, combine four prefix corners.
- 4Check boundary sentinels carefully.
Concrete example
Query a rectangle after building a matrix prefix table.
- 1Take the bottom-right prefix.
- 2Subtract regions above and left.
- 3Add the overlap back once.
Four prefix values answer each rectangle in O(1).
What must remain true (Loop Invariant)
prefix[r][c] stores the aggregate over the rectangle above and left of (r,c).
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Build / query
O(rows×cols) / O(1)
O(rows×cols)
Four cumulative corners answer a rectangle.When to use it
- Range queries, range updates, directional products, and best contiguous scores.
- Replacing repeated range scans with cumulative state.
- Combining left and right summaries.
Common mistakes
- Mixing inclusive and exclusive prefix conventions.
- Using zero as Kadane’s base when a non-empty all-negative answer is required.
- Subtracting the wrong boundary or forgetting a neutral prefix.
Practice prompts
- Reproduce the worked 2D prefix sums example without looking at the trace.
- Change one input condition and explain whether the 2D prefix sums invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.