Range Sum Query 2D - Immutable
Answer rectangle sum queries on a matrix.
Pattern fit
This is the natural 2D extension of prefix sums, where inclusion-exclusion lets you isolate any rectangle in O(1).
Key observation
Every rectangle sum is the big prefix minus two overlaps plus the shared corner prefix.
Target complexity
O(1) query / O(mn)
How to break down the solution cleanly
This is the natural 2D extension of prefix sums, where inclusion-exclusion lets you isolate any rectangle in O(1).
Every rectangle sum is the big prefix minus two overlaps plus the shared corner prefix.
Define what the cumulative state means.
Build the prefix in one forward pass.
Reference implementation
Python# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
Common pitfalls
Forgetting the overlap term in inclusion-exclusion.
Mixing row/column offsets when building the prefix matrix.
Common follow-ups
How would mutable updates change the structure?
Why is the prefix grid usually one row and column larger?
Continue with related problems
Build repeatable depth inside the Prefix Sum cluster before moving on.