0

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.
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 = 6
One 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