Skip to content
Back to AlgorithmsAll lessons

Algorithms

Prefix Sums

O(n) time to build the prefix array once · O(1) time per range-sum question afterward, down from O(n) per question without it · O(n) space for the prefix array.

The idea, in plain English

Think of a car's odometer readings at every mile marker. To find the distance between mile 20 and mile 50, you do not re-measure the road. You just subtract two odometer readings. A prefix sum array does the same trick for a list of numbers. Compute the running totals once, and any 'sum of this range' question becomes a single subtraction.

How it works

  1. 1Build a prefix array, where prefix[i] holds the sum of all original items before position i. Prefix[0] is 0, since nothing is summed yet.
  2. 2To get the sum of a range from position 'left' to 'right' (including both ends), take prefix[right + 1] minus prefix[left].
  3. 3Reuse the same prefix array for as many range-sum questions as you like. Each one now takes one subtraction instead of a fresh loop.

When you'd use it

Use it to answer many 'sum of this range' questions on data that does not change — analytics dashboards, spreadsheet-style range totals, or any repeated range-sum question where adding up the range each time would be too slow.

Common beginner mistakes

  • Making off-by-one errors. Prefix[i] is the sum before position i, so the range [left, right] needs prefix[right + 1] minus prefix[left], not prefix[right] minus prefix[left].
  • Rebuilding the prefix array on every question instead of once up front, which throws away the whole speed benefit.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Numbers: 2 4 6 8 10
Sum of indices 1..3: 18
Sum of indices 0..4: 30

See it in motion

Build once, answer fastPrefix sumsO(n) time to build the prefix array once · O(1) time per range-sum question afterward, down from O(n) per question without it · O(n) space for the prefix array.

prefix[0] = 0 — nothing summed yet. Press play to build.

0
Running total
[2, 5]
Query range
—
Answer
0/11
Step
Building / prefix[R+1]prefix[L]Queried rangeNot yet used

Not sure this is the right topic? See the learning paths → or where this leads →