Prefix Sum
Store running totals once, and any range sum becomes two lookups and a subtraction.
Result · step 9 of 11Prefix Sum and Kadane: Range sum from prefix totals
prefix[7] = prefix[6] + a[7] = 25 + 6 = 31.
What you will see
A second row fills left to right; a range query highlights two prefix cells and their difference.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(n) |
O(1) per query after O(n) build.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each cell is announced as index, value and state; each step's accessibility text states the decision and its effect.
Reduced motion: Swaps and shifts become value crossfades with an outline flash; pointers appear at their destination.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Prefix Sum and Kadane covers these too, in the same run.