cf.completefrontend
ARRAYS & HASHING · FOUNDATION

Prefix sums

Store running totals once, so the sum of any range of an array takes one subtraction.

Time O(n) to build, O(1) per rangeSpace O(n)15 practice problemsStep-through picture

The idea

Suppose you need the sum of many different ranges of the same array: the sales from day 3 to day 10, then from day 5 to day 6, and so on. Adding up each range separately takes as many steps as the range is long.

A prefix sum array stores running totals: prefix[i] is the sum of the first i numbers. Building it takes one pass. After that, the sum of any range from left to right is prefix[right + 1] - prefix[left]: the total up to the end of the range, minus the total before it starts.

prefix has one more slot than nums, and prefix[0] is 0, the sum of no numbers. That extra slot means ranges that start at index 0 need no special case.

An everyday example

Reading a car's odometer

A car's odometer shows the total distance it has ever driven. To know how far you drove today, you don't add up every street you took. You subtract this morning's reading from tonight's. Any trip's length is the reading at its end minus the reading at its start, and that works for any trip, however long.

How the example maps to the code
In the exampleIn the code
The odometer reading at each momentprefix[i], the total of the first i numbers
Driving one more streetprefix[i + 1] = prefix[i] + nums[i]
The reading before the trip startsprefix[left]
The trip's lengthprefix[right + 1] - prefix[left]

From the slow way to prefix sums

  1. The obvious way to answer "what is the sum from left to right?" is a loop that adds those numbers. A range can be n numbers long, so q questions cost up to n × q additions. For 1,000 questions on 100,000 numbers, that is 100 million additions.
  2. Much of that work repeats. Two overlapping ranges add the same middle numbers again, and a range that starts at index 0 redoes everything an earlier range from 0 already added. The answers share parts, but the loop throws each part away.
  3. Every range sum is a difference of two sums that start at index 0: the sum up to right, minus the sum of the part before left. So only n + 1 numbers are needed in total, the sums of the first 0, 1, 2, and up to n numbers.
  4. Each of those sums is the one before it plus one more number, so a single pass builds them all. Put 0 in front for the sum of no numbers, and every range becomes one subtraction. Build once, then subtract for each question: that loop is prefix sums.

How it works

  1. Create prefix with nums.length + 1 zeros. prefix[0] stays 0.
  2. Walk i from 0 to the end: prefix[i + 1] = prefix[i] + nums[i].
  3. Now prefix[i] is the sum of nums[0] through nums[i - 1].
  4. To get the sum from left to right (both included), take prefix[right + 1] - prefix[left].
  5. Each range question is now one subtraction, whatever its length.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function buildPrefix(nums) {
  2. const prefix = new Array(nums.length + 1).fill(0);
  3. for (let i = 0; i < nums.length; i++) {
  4. prefix[i + 1] = prefix[i] + nums[i];
  5. }
  6. return prefix;
  7. }
  9. function rangeSum(prefix, left, right) {
  10. return prefix[right + 1] - prefix[left];
  11. }

How fast it is

TimeO(n) to build, O(1) per range
Extra memoryO(n)

Building visits each number once. Each range sum is one subtraction of two stored totals. The prefix array has n + 1 numbers.

  • Best caseO(1)

    Answering a question once prefix exists: one subtraction, whether the range has 1 number or 100,000.

  • Average caseO(n + q)

    Building once in n steps and then answering q questions in one step each.

  • Worst caseO(n)

    A single question on a fresh array. Building costs n steps, so for one question prefix sums are no faster than adding the range directly.

Common mistakes

  • Mixing up the shift: the range left..right is prefix[right + 1] - prefix[left], not prefix[right] - prefix[left].
  • Making prefix the same length as nums, which forces special cases for ranges that start at 0.
  • Rebuilding the prefix array for every question, which throws away the whole benefit.
  • Using prefix sums when the array changes between questions. Each change would mean rebuilding; use a Fenwick tree instead.

When to use it

Look for these clues in a problem:

  • Many questions ask for the sum (or count) of a range left..right of the same array.
  • The problem mentions running totals, cumulative values, or a balance over time.
  • You need the sum of everything to the left and to the right of each index.
  • The array doesn't change between questions (if it does, look at a Fenwick tree).

Check yourself

Answer each one in your head first, then open it.

For nums = [4, -2, 7, 0, 3], what is rangeSum(prefix, 2, 4)?

prefix[5] - prefix[2] = 12 - 2 = 10, which matches 7 + 0 + 3.

Why can't prefix maximums answer "largest number from left to right"?

Subtraction undoes a sum, but nothing undoes a maximum. Knowing the largest of the first 5 numbers and of the first 2 doesn't tell you the largest of numbers 3 to 5.

How many additions does building prefix take for 1,000 numbers, and how many steps for 500 questions?

1,000 additions to build, then 500 subtractions, one per question.

When all numbers are non-negative, what extra property does prefix have?

It never goes down, so it is sorted. That lets you binary search it, for example for the first position where the running total reaches a target.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 15 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The build keeps one rule: after the loop step for index i, prefix[i + 1] equals nums[0] + ... + nums[i]. Before the loop, prefix[0] is 0, the sum of no numbers. Each step adds exactly one more number to the total before it, so the rule holds for every slot when the loop ends.

For any left <= right, prefix[right + 1] adds up nums[0..right], and prefix[left] adds up nums[0..left - 1], which is the first part of the same list. Subtracting removes exactly that first part and leaves nums[left..right]. Only adding and subtracting are used, so negatives and zeros need no care.

The trick needs two things. The array must not change after prefix is built, or the stored totals go stale. And the operation must be undoable: you can take a sum away with subtraction, or an XOR away with another XOR. Taking a maximum can't be undone, so prefix maximums can't answer "largest number from left to right".

Going deeper

4 more ideas

Why the subtraction gives the range

prefix[right + 1] is nums[0] + ... + nums[right]. prefix[left] is nums[0] + ... + nums[left - 1]. Subtracting cancels every number before left, leaving exactly nums[left] + ... + nums[right].

Why the extra zero at the front

Without prefix[0] = 0, a range starting at index 0 would need prefix[left - 1], which is prefix[-1], so you'd need an if. Shifting everything by one slot makes every range use the same formula. It's the most common source of off-by-one bugs, so keep the rule in mind: prefix is one longer than nums.

Variations

The same trick works for anything you can add and take away: counts (how many errors happened between two times), running products (careful with zeros), and XOR. Combined with a hash map, it finds ranges with a given sum. In two dimensions it gives the sum of any rectangle.

Cost

Building takes O(n) time and O(n) space. Each range question then takes O(1). With q questions, the total is O(n + q) instead of O(n * q) for adding up each range.

Work it by hand

Every step in a table, with why

Build the running totals of five numbers, including a negative and a zero, then answer two range questions.

nums = [4, -2, 7, 0, 3]

StepStepReadsWritesprefix afterWhy
1i = 0prefix[0] = 0, nums[0] = 4prefix[1] = 4[0, 4, 0, 0, 0, 0]prefix starts as six zeros, one more slot than nums. The first total is 0 + 4.
2i = 1prefix[1] = 4, nums[1] = -2prefix[2] = 2[0, 4, 2, 0, 0, 0]A negative number makes the running total go down. Nothing special is needed.
3i = 2prefix[2] = 2, nums[2] = 7prefix[3] = 9[0, 4, 2, 9, 0, 0]prefix[3] is the sum of the first three numbers: 4 - 2 + 7 = 9.
4i = 3prefix[3] = 9, nums[3] = 0prefix[4] = 9[0, 4, 2, 9, 9, 0]A zero leaves the total unchanged, so two neighboring totals are equal.
5i = 4prefix[4] = 9, nums[4] = 3prefix[5] = 12[0, 4, 2, 9, 9, 12]The last slot holds the sum of the whole array, 12. Building is done after 5 additions.
6rangeSum(prefix, 1, 3)prefix[4] = 9, prefix[1] = 4returns 9 - 4 = 5unchangedThe total up to index 3, minus the total before index 1, leaves -2 + 7 + 0 = 5.
7rangeSum(prefix, 0, 4)prefix[5] = 12, prefix[0] = 0returns 12 - 0 = 12unchangedA range starting at index 0 subtracts prefix[0], which is 0. No special case is needed.

prefix is [0, 4, 2, 9, 9, 12], built with 5 additions. Each question then costs one subtraction, however long its range: 5 for indexes 1 to 3 and 12 for the whole array.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Prefix sumsO(n + q)O(n)The array doesn't change and you'll ask many range questions about it.
Add up each rangeO(n · q)O(1)Only one or two questions, or the array changes all the time.
Fenwick treeO(q log n)O(n)Values change between questions, so each update and each sum must be fast.

Extra memory: O(n): prefix holds n + 1 numbers. You could write the totals into nums itself to save memory, but that destroys the input.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Prefix sums and the other approaches, on a scale where each line up is 10 times more steps.
  • Prefix sums O(n + q)
  • Add up each range O(n · q)
  • Fenwick tree O(q log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Prefix sums202,0002 million
Add up each range1001 million1 trillion
Fenwick tree339,96620 million

Inputs that need care

5 tricky inputs
An empty array: nums = []
prefix is [0]. No range with left <= right exists, so there is nothing to ask. rangeSum(prefix, 0, -1) returns 0, the sum of an empty range.
A range of one number: left = right = 2
prefix[3] - prefix[2] is 9 - 2 = 7, which is just nums[2].
left > right: rangeSum(prefix, 3, 1)
It returns prefix[2] - prefix[3] = 2 - 9 = -7, a meaningless number. Check the order, or swap the two indexes, before calling.
An index past the end: right = nums.length
prefix[right + 1] is undefined, and the subtraction gives NaN. Check bounds at the edge of your code.
Very large totals, past 2^53
JavaScript numbers lose exact whole-number precision there, so totals can be off. Use BigInt for the totals when values are that large.

Variations and follow-ups

Twists interviewers add

Product of everything except yourself

Build running products from the left and from the right. The answer at i is the product of everything before i times the product of everything after it. This avoids dividing, which breaks when a number is zero.

Balance point

To find an index where the sum on its left equals the sum on its right, compare prefix[i] with prefix[n] - prefix[i + 1] for each i. One build and one pass answer it in O(n).

Values that change: a Fenwick tree

If numbers change between questions, each change would force a rebuild. A Fenwick tree stores partial totals so that both a change and a range sum take O(log n) steps.

Weighted random pick

With non-negative weights, prefix only goes up, so it is sorted. Draw a random number below the total and binary search prefix for the first total above it. Heavier items cover wider stretches, so they're picked more often.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "sum of the subarray from i to j", "many range queries", or a hint that the array never changes.
  • Say the definition out loud: "prefix[i] is the sum of the first i numbers, so the range is prefix[right + 1] - prefix[left]." Saying "first i numbers" settles the off-by-one question.
  • Test three ranges by hand: one starting at index 0, one of a single number, and the whole array.
  • The usual follow-up is "what if numbers can change?". Answer: a Fenwick tree or a segment tree, with O(log n) per update and per query. Another is "and in two dimensions?": 2D prefix sums.

Where frontend code uses it

The same idea in real UI code
  • Virtualized lists with rows of different heights keep running totals of the heights, so the top position of row i is prefix[i].
  • Code editors keep the character offset where each line starts, which is a prefix sum of line lengths, to turn an offset into a line and column.
  • Charts that show cumulative totals (revenue to date, total sign-ups) plot a prefix sum of the daily numbers.

Related algorithms