When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Repeated range sums
- Subarray total conditions
When another approach fits better
- Only one simple scan result is needed
- Updates occur between queries and a static prefix table would become stale
How it works#
Rescan every requested range or enumerate each subarray and sum it again.
Add an explicit zero-length prefix.
Write the range equation before code.
For target-subarray counts, store prior prefix frequencies and query the needed difference before updating.
Invariantprefix[i] represents the aggregate of exactly the first i elements, so a range is the difference of two boundaries when the operation permits it.
Example and template#
Range Sum Query - Immutable
Makes the preprocessing-versus-query trade-off explicit.
Open the full problem brief- Boundaries
P0=0, P1=3, P2=8, P3=6Each prefix ends before the matching input index boundary.
- Range [1,2]
P3 − P1 = 3Subtract the prefix before left from the prefix after right.
prefix[0] = 0
for i in 0..n-1:
prefix[i + 1] = prefix[i] + input[i]
range_sum(left, right_inclusive) = prefix[right + 1] - prefix[left]- Time
- O(n) preprocessing; O(1) per static range query
- Space
- O(n), or O(k) map state for counting
- Assumptions
- The aggregate supports a difference/inverse and input is not updated after preprocessing.
Pitfalls#
Common wrong approaches
Ranges beginning at index zero need a special case and count logic misses empty-prefix matches.
Mixing element indices and prefix boundaries creates off-by-one subtraction.
Edge cases
- Range begins at zero
- Empty range contract
- Negative totals
- Integer overflow in cumulative state
Interview narration
- “Each query repeats the same work from the front.”
- “I will store n+1 boundary totals, including the empty prefix.”
- “Then this inclusive range is prefix[right+1] minus prefix[left].”
Practice#
Range Sum Query - Immutable
Makes the preprocessing-versus-query trade-off explicit.
Practice this problemCount contiguous spans whose number of wins equals losses.
Reveal the pattern decision
Map wins/losses to +1/−1 and count equal prior prefix balances with a frequency map.
Transfer problem
Answer immutable rectangle-sum queries over a matrix.
Checkpoint: Derive a 2-D inclusion-exclusion boundary formula and test the top and left edges.
Follow-up variations
- Support point updates with a Fenwick or segment tree
- Return one matching subarray rather than the count
Error-log prompts
- What did prefix index i include?
- Did I seed the empty prefix correctly?