Prefix Sum and Kadane
Carry one number along the array and update it at every slot. Prefix sum carries the total so far. Kadane carries the best run ending here. Both replace a nested loop with a single pass.
How many subarrays add up to 7? A subarray from j + 1 to i sums to prefix[i] - prefix[j], so it hits 7 exactly when some earlier prefix equals prefix[i] - 7. Keep a count of every prefix seen so far, starting with 0 for the empty prefix, and each index answers in one lookup.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
Prefix is now 3 and the target is 7. Has prefix -4 been seen before?
Answer: No, nothing ends here. -4 is not among the recorded prefixes.
Prefix is now 7 and the target is 7. Has prefix 0 been seen before?
Answer: Yes, a subarray ends here. 0 was recorded, so the values after it up to here sum to 7.
Prefix is now 14 and the target is 7. Has prefix 7 been seen before?
Answer: Yes, a subarray ends here. 7 was recorded, so the values after it up to here sum to 7.
Prefix is now 16 and the target is 7. Has prefix 9 been seen before?
Answer: No, nothing ends here. 9 is not among the recorded prefixes.
Prefix is now 10 and the target is 7. Has prefix 3 been seen before?
Answer: Yes, a subarray ends here. 3 was recorded, so the values after it up to here sum to 7.
Prefix is now 11 and the target is 7. Has prefix 4 been seen before?
Answer: No, nothing ends here. 4 is not among the recorded prefixes.
Prefix is now 15 and the target is 7. Has prefix 8 been seen before?
Answer: No, nothing ends here. 8 is not among the recorded prefixes.
Prefix is now 17 and the target is 7. Has prefix 10 been seen before?
Answer: Yes, a subarray ends here. 10 was recorded, so the values after it up to here sum to 7.
How it runs, step by step
How many subarrays add up to 7? A subarray from j + 1 to i sums to prefix[i] - prefix[j], so it hits 7 exactly when some earlier prefix equals prefix[i] - 7. Keep a count of every prefix seen so far, starting with 0 for the empty prefix, and each index answers in one lookup.
Counting subarrays with sum 7 over 8 values.
i = 0: prefix becomes 3, so a subarray ending here sums to 7 if an earlier prefix was 3 - 7 = -4. Never seen, so none ends here. Then record prefix 3.
Index 0, prefix 3, count 0.
i = 1: prefix becomes 7, so a subarray ending here sums to 7 if an earlier prefix was 7 - 7 = 0. Seen 1 time, before the start: count rises to 1. Then record prefix 7.
Index 1, prefix 7, count 1.
i = 2: prefix becomes 14, so a subarray ending here sums to 7 if an earlier prefix was 14 - 7 = 7. Seen 1 time, after index 1: count rises to 2. Then record prefix 14.
Index 2, prefix 14, count 2.
i = 3: prefix becomes 16, so a subarray ending here sums to 7 if an earlier prefix was 16 - 7 = 9. Never seen, so none ends here. Then record prefix 16.
Index 3, prefix 16, count 2.
i = 4: prefix becomes 10, so a subarray ending here sums to 7 if an earlier prefix was 10 - 7 = 3. Seen 1 time, after index 0: count rises to 3. Then record prefix 10.
Index 4, prefix 10, count 3.
i = 5: prefix becomes 11, so a subarray ending here sums to 7 if an earlier prefix was 11 - 7 = 4. Never seen, so none ends here. Then record prefix 11.
Index 5, prefix 11, count 3.
i = 6: prefix becomes 15, so a subarray ending here sums to 7 if an earlier prefix was 15 - 7 = 8. Never seen, so none ends here. Then record prefix 15.
Index 6, prefix 15, count 3.
i = 7: prefix becomes 17, so a subarray ending here sums to 7 if an earlier prefix was 17 - 7 = 10. Seen 1 time, after index 4: count rises to 4. Then record prefix 17.
Index 7, prefix 17, count 4.
4 subarrays sum to 7. One pass with a hash map of prefix counts: O(n) instead of the O(n squared) of trying every pair of ends, and negative values are no problem because prefixes are looked up, not scanned.
4 subarrays found.
Write it yourself
Define rangeSum(values, start, end) and return the sum of values[start] through values[end], both included. It runs in your browser against this lesson's own 3 examples.
// Build the running totals once, then any range is one subtraction - or just add the range up.function rangeSum(values, start, end) { return 0;}
Remember
- Prefix sums cost O(n) once, then every range sum is two lookups and a subtraction.
- Kadane's rule: a negative run can only hurt whatever it touches, so drop it and start over.
- Both are one pass. If you find yourself summing the same slots twice, one of these applies.
Topics covered
Related
Where this is used
Computer visionIntegral images in face detection
A summed-area table is a prefix sum in two dimensions: each cell holds the total of everything above and to the left of it. The sum inside any rectangle is then four lookups and a little arithmetic no matter how large the rectangle is, which is what lets the Viola-Jones detector in OpenCV score thousands of rectangle features per frame. The same table gives a box blur whose cost does not grow with the blur radius.
DatabasesRunning totals in SQL window functions
SUM(amount) OVER (ORDER BY day) is a prefix sum, and PostgreSQL evaluates it the way this lesson does: the window node carries one accumulator down the sorted rows instead of re-adding the whole frame for each row. Without that, a running total over n rows degenerates into a self-join that revisits every earlier row, which is n-squared work for an n-row answer.
OperationsCounter metrics in Prometheus
A Prometheus counter only goes up, apart from resetting to zero when the process restarts: it stores the prefix sum of events rather than the count per interval. rate() and increase() recover the traffic inside a window by subtracting the sample at its start from the sample at its end, which is exactly the p[r] - p[l - 1] step, with the pre-reset total added back whenever a drop reveals a restart. Storing the total instead of per-interval deltas is also why one missed scrape loses nothing - the next sample still subtracts correctly across the gap.
BioinformaticsLocal alignment in sequence search
Smith-Waterman scores partial alignments and clamps every cell at zero, so a prefix whose score has gone negative is dropped and the alignment restarts there. That max(0, ...) is Kadane's rule applied along the alignment, and it is the one change from global alignment. It is what makes the algorithm report a strong matching stretch buried inside two sequences that do not match overall.
Why it works this way
Why prefix sums need a value that means 'nothing yet'
rangeSum special-cases l == 0, and countSubarrays seeds the map with prefix 0 already seen once. Both are the same fix: a subarray starting at index 0 has no earlier prefix to subtract, so you have to supply one. The common alternative is to build p with n + 1 slots and p[0] = 0, after which p[r + 1] - p[l] works with no branch at all - you trade one extra slot for an off-by-one you then carry everywhere.
Prefix sums cannot answer range minimum or maximum
Range sum works only because subtraction undoes addition. The maximum of the first r values and the maximum of the first l - 1 tell you nothing about the maximum between them, because max has no inverse. Operations you can undo are fine: sum and xor always, product only when no element is zero, since you cannot divide a zero back out. Minimum, maximum and gcd have no inverse at all, which is why range minimum needs a sparse table or a segment tree rather than a prefix array.
Kadane returns 0 on an all-negative array if you seed it wrong
Starting with endingHere = 0 and best = 0 quietly answers a different question: best sum including the empty subarray. An array of all negatives then gives 0 instead of its largest element. Seeding both from a[0] and looping from i = 1, as the code here does, forces a non-empty answer. Decide which version the problem wants before writing the loop, because both are correct answers to different questions.
Why counting subarrays needs a map instead of a sliding window
When every value is positive the running sum grows as the window widens, so two pointers can expand and shrink to hunt for k. A single negative value breaks that: the sum is no longer monotone in the window's width, so shrinking from the left can step straight past the target and there is nothing left to steer the pointers by. The prefix map sidesteps the ordering entirely by remembering every prefix seen so far and asking how many of them equal prefix - k.
Read more
- Prefix sumWikipedia
- Maximum subarray problemWikipedia
- Summed-area tableWikipedia
- Static Range Sum QueriesCSES 1646 · cses.fi
- Maximum Subarray SumCSES 1643 · cses.fi