AlgoScope

Prefix Sum and Kadane

algorithmintermediateTime O(n)Space O(1) for Kadane, O(n) for prefix sums

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.

3011421354952667

Turn the array into running totals, so that any range sum becomes two lookups. Then sum indices 2 to 5 without touching the values in between.

How it runs, step by step

  1. Turn the array into running totals, so that any range sum becomes two lookups. Then sum indices 2 to 5 without touching the values in between.

    Building prefix sums over 8 values, then summing indices 2 to 5 from them.

  2. Index 0 is its own total, 3.

    Index 0 keeps its value 3 as the first running total.

  3. prefix[1] = prefix[0] + a[1] = 3 + 1 = 4.

    Index 1 becomes 3 plus 1, which is 4.

  4. prefix[2] = prefix[1] + a[2] = 4 + 4 = 8.

    Index 2 becomes 4 plus 4, which is 8.

  5. prefix[3] = prefix[2] + a[3] = 8 + 1 = 9.

    Index 3 becomes 8 plus 1, which is 9.

  6. prefix[4] = prefix[3] + a[4] = 9 + 5 = 14.

    Index 4 becomes 9 plus 5, which is 14.

  7. prefix[5] = prefix[4] + a[5] = 14 + 9 = 23.

    Index 5 becomes 14 plus 9, which is 23.

  8. prefix[6] = prefix[5] + a[6] = 23 + 2 = 25.

    Index 6 becomes 23 plus 2, which is 25.

  9. prefix[7] = prefix[6] + a[7] = 25 + 6 = 31.

    Index 7 becomes 25 plus 6, which is 31.

  10. Sum of 2 to 5 is prefix[5] minus prefix[1]: everything up to 5, less everything before 2.

    The range sum is prefix at 5 minus prefix at 1.

  11. 23 - 4 = 19. Two lookups and one subtraction, however long the range. Building the totals cost O(n) once; every query after that is O(1).

    The sum of indices 2 to 5 is 19.

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;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

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

Next up