Micro-questions over the prefix sum pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. State the pattern in one sentence, using the bank analogy.
Answer
A bank statement does not store “how much did I spend in June” — it stores the running balance after every transaction, and you get June by subtracting the balance on 1 June from the balance on 30 June.
2. State it without the analogy.
Answer
Do not store the answers to ranges; store the totals up to each point, and subtract.
3. Why is summing a range directly “fine — once”?
Answer
Because the work is per query, and the queries are the thing you have a lot of. A dashboard re-adds the same numbers hundreds of times a second as the slider moves.
4. Why does the subtraction work exactly?
Answer
Everything before the start got counted into both totals, so subtracting cancels it out exactly, and what survives is precisely the slice you asked for.
5. What is the cost of a query, and what does it depend on?
Answer
Two array lookups and a subtraction — and it does not matter whether the range is 4 days or 4 years.
B. The vocabulary
6. What is a sentinel here, and what does it buy?
Answer
A leading 0 meaning “nothing so far”, so index 0 needs no special case. The opening balance.
7. What is preprocessing?
Answer
Work done once up front so later queries are cheap.
8. What is a summed-area table?
Answer
The 2-D version — totals from the origin to each cell.
9. What is inclusion–exclusion?
Answer
Subtracting overlapping regions, then adding back what was removed twice.
10. What is this operation called in parallel computing?
Answer
Scan.
C. Where it shows up
11. Where is it in SQL?
Answer
SUM(revenue) OVER (ORDER BY date) — running totals, cohort charts and burndown charts are all prefix sums, and time-series databases pre-materialise them.
12. What is an integral image, and what famous thing used it?
Answer
The summed-area table in image processing — sum of pixels in any rectangle in constant time. Box blur uses it, and so did the Viola–Jones face detector, which is why real-time face detection worked on 2001 hardware.
13. How does weighted random selection use it?
Answer
Take prefix sums of the weights, pick a random number in , and binary search for where it lands — , proportional to weight. Ad bidding, game loot tables and weighted A/B bucketing.
14. Why is the parallel version surprising?
Answer
It looks hopelessly sequential — each total depends on the one before — yet it parallelises in depth, underpinning stream compaction, radix sort and parallel memory allocation.
D. The mechanics
15. Define P[i] in the sentinel convention.
Answer
The sum of everything before index i. So P[0] = 0.
16. Write the range query.
Answer
def range_sum(prefix, i, j): # nums[i..j] inclusive
return prefix[j + 1] - prefix[i]17. Write the 2-D build step and explain its last term.
Answer
S[r][c] = grid[r][c] + S[r-1][c] + S[r][c-1] - S[r-1][c-1]The corner block is included in both the “above” and “left” totals, so it is subtracted once.
18. Write the 2-D rectangle query.
Answer
sum = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]
The + is there because the top-left block got subtracted twice — once by each strip.
E. The hash-map variant
19. What question do plain prefix sums answer, and what is the harder reverse?
Answer
Plain: “what is the sum of this range I am naming?” Reverse: “is there any range summing to ?” — Subarray Sum Equals K.
20. Do the rearrangement.
Answer
21. What does that turn the question into?
Answer
“Have I seen the prefix sum before, and how many times?” — a hash-map lookup, not a search.
22. Why does seen start as {0: 1}?
Answer
The empty prefix, so subarrays starting at index 0 are counted.
23. What replaced the array, and why?
Answer
A hash map of prefix sum → count, because you no longer care where the prefixes were, only that they existed.
24. Re-skin 1: longest subarray with equal 0s and 1s.
Answer
Count each 0 as , so “equal counts” becomes “sum is zero”, which becomes “this prefix sum has appeared before”. Store the first index each sum was seen at; the distance between sightings is the subarray.
25. Re-skin 2: subarray sums divisible by .
Answer
Store running % k instead of running. Two positions with the same remainder bracket a subarray divisible by .
26. State the general shape.
Answer
Transform the elements so the property you want becomes “sum is 0” or “sums are equal”, then let the hash map find repeats.
F. Complexity and gotchas
27. Give the costs.
Answer
to build, per query. For queries that is instead of . Space — or a scalar plus a map in the streaming variants.
28. What is the number-one bug?
Answer
Inclusive vs exclusive off-by-ones. Pick the sentinel-padded convention and stay in it; mixing conventions mid-problem is how range_sum quietly returns a number one element too big.
29. Which operations can prefix sums handle, and which cannot?
Answer
Invertible ones — sum, XOR, count — because you can subtract off the part you do not want. Max and min cannot: knowing max(A[0..5]) and max(A[0..1]) tells you nothing about max(A[2..5]).
30. So what do you use for range max?
Answer
A sparse table or segment tree — or, as in Trapping Rain Water, directional prefix/suffix maxima arrays that you read rather than subtract.
31. What happens if the array can be updated?
Answer
One update to nums[i] invalidates every prefix sum from i onward. With frequent updates use a Fenwick tree or segment tree — for both update and query.
32. What is the overflow risk?
Answer
The prefix sums grow to the total of the whole array, which can exceed int even when every element is small. Use 64-bit.
33. When should you not use the pattern?
Answer
With only one query to answer. Preprocessing costs and a single range sum also costs — it only pays amortised over many queries.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Prefix Sum — the pattern
- Sliding Window — Question Bank — what it cannot replace when values go negative
- Hash Maps — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering