DSA & Implementation · core
Prefix Sums
Precomputed cumulative arrays that turn repeated range queries into O(1) lookups.
Mental model
A prefix array trades one O(n) pass for O(1) range answers afterwards: sum(i..j) becomes prefix[j+1] - prefix[i]. The generalisation matters more than the trick — any associative, invertible operation works, and the difference array is the same idea run backwards, letting you apply many range updates in O(1) each and materialise the result once.
How to study Prefix Sums
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Prefix Sums with Sliding Window, Two Pointers. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Answer range-sum queries in O(1) and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Range queries in analytics, 2D image integral images, and the setup step for many subarray problems.
Common mistakes
- Off-by-one from mixing inclusive and exclusive bounds — fix the convention once and keep it
- Using it for min or max, which are associative but NOT invertible, so subtraction is meaningless (use a sparse table instead)
- Rebuilding the prefix array inside the query loop, which throws away the whole benefit
- Overflow on long integer ranges when the running sum exceeds the element type
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Answer range-sum queries in O(1)
Implement makeRangeSum(nums) returning a function query(i, j) that gives the inclusive sum of nums[i..j] in O(1) per call. Build the prefix array once.
Expected evidence: const q = makeRangeSum([1,2,3,4,5]); q(1,3) -> 9; q(0,4) -> 15
Open the interactive drill →Review prompts
- Prefix sums answer range-sum in O(1). Why does the same trick fail for range-minimum, and what does that tell you about which operations it works for?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.