0
Challenge · 27Array & String Patterns
Prefix sums
Patternsused in ~80% of apps
Answer a thousand questions about totals without ever adding a range up. You pay once, up front, and every question afterwards costs one subtraction.
Core idea. Precompute the running total from the start up to every position. Then the total of any range is just one running total minus another, no loop, no matter how wide the range is.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
nums = [3, 1, 4, 1, 5] → prefix
nums
3
1
4
1
5
prefix
0
3
4
8
9
14
P0P1P2P3P4P5
sum of positions 1 through 3 (the 1, 4, 1) =
P4 − P1 = 9 − 3 = 6One subtraction. The width of the range never enters into it.
The prefix array has one extra slot, and it starts with 0. That leading zero is what makes ranges beginning at index 0 work without a special case.
↑ play a little first, then dig in