Prefix Sums
Easy+70 XPPrecompute running totals once, then answer any range-sum in O(1) with a single subtraction.
No visualization loaded.
Watch
—
Press Run to begin.
A prefix sum is a running total. prefix[i] is the sum of everything in the array up to (but not including) position i — so prefix[0] = 0, prefix[1] = first value, prefix[2] = first two values added, and so on. Building that takes one quick pass. The payoff: once you have the running totals, the sum of ANY chunk of the array — say positions 2 through 5 — is just one subtraction: the running total at the end minus the running total before the start. No looping over the chunk; the answer pops out instantly.
▸What's a prefix sum?
It's the total of all the values from the start of the array up to a given spot. If the array is [3, 1, 4, 1], the prefix sums are 0, 3, 4, 8, 9 — each one is the previous running total plus the next value. We tuck a 0 at the front (the 'sum of nothing') so the range formula always works without a special case.
▸How does it make range-sum queries O(1)?
The sum of positions l through r equals prefix[r+1] - prefix[l]. Why? prefix[r+1] is 'everything up to and including r' and prefix[l] is 'everything before l'. Subtract, and the overlap cancels, leaving exactly the chunk in the middle. That's one subtraction — constant time — no matter how big the range is. Without prefix sums you'd add up the whole range each time, which is O(n) per query.
▸What's the setup cost?
One pass over the array to build the running totals — O(n) time and O(n) extra space for the prefix array. You pay that once. After that, every range-sum query is free-ish (O(1)). So it's a brilliant trade when you'll ask many range-sum questions: the setup cost is shared across all of them.
▸When do I reach for prefix sums?
Whenever you'll repeatedly ask 'what's the total between here and there?' — running balances, sub-array sums, image/area lookups (a 2D version exists too), or as a building block in harder problems. If you only ask once, a plain loop is fine. If you ask again and again, precompute prefix sums and turn each answer into a subtraction.
How the work grows
O(n) build, O(1) per query is fair — grows in step with the data. One pass builds the running totals (O(n)). After that each range-sum is a single subtraction (O(1)), no matter the range size — so the more queries you ask, the more that one-time setup pays off. The cost is O(n) extra space to store the prefix array.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.