Adding up any stretch of a list in one step

Tier 1Free

Elman HuseynovUpdated 2026-10-21

Level

Where it runs

1. The problem

In the last few lessons a window moved along a list and the sum was updated on the way. That works when there is one window and it moves in one direction. A dashboard is different. It asks hundreds of questions, each about its own stretch of the list, unrelated to the others. A sliding window can't help here.

You have a metrics dashboard (a screen that shows numbers about your system). There is one number per minute: requests, bytes, errors, whatever you measure. The user moves a time slider and asks how many requests there were in total from minute 40 to minute 90. You add up those 51 numbers and show the answer.

Then the user moves the slider again: minute 5 to minute 800. You add up 796 numbers. Another move, and you add up a new stretch from zero again. The slider sends a new range every few pixels of mouse movement, and each time you add up thousands of numbers again. There is a way to answer any "sum from here to there" with one subtraction, however long the range is.

2. In plain words

Some shop receipts print, next to each item, the total so far. Say you want to know what three items in the middle of the receipt cost together. You don't add them up again. Take the total printed after the third of them and subtract the total printed right before the first. The difference is the price of those three items.

That is the whole method. Write down the total so far at every position, once. After that, the sum of any stretch is one total minus another. That is one subtraction, however long the stretch is.

3. The idea

Walk the list once and keep a running total: after each number, write down the sum of all numbers up to and including it. Call this list of running totals prefix.

The main rule: the sum of a stretch is the running total at its end minus the running total right before its start. Everything before the start of the stretch disappears in the subtraction. What is left is exactly the stretch you asked for.

To make the indices line up, start the list with a zero, before the first number. Then prefix[0] = 0, and each next cell is the previous one plus the next number: prefix[i] = prefix[i-1] + nums[i-1]. Now prefix[i] means "the sum of the first i numbers". The sum of the range from l to r (both ends included) is:

prefix[r+1] - prefix[l]

Thanks to the starting zero, a range that begins at the very first position uses the same formula, with no special case. Without that zero, every range would be off by one position.

Trace it on nums = [2, 4, 1, 3].

Build prefix: 0, then 0 + 2 = 2, then 2 + 4 = 6, then 6 + 1 = 7, then 7 + 3 = 10. That gives prefix = [0, 2, 6, 7, 10].
The range [1, 3] (the numbers 4, 1, 3): prefix[4] - prefix[1] = 10 - 2 = 8. Check: 4 + 1 + 3 = 8.
The range [0, 0] (just the 2): prefix[1] - prefix[0] = 2 - 0 = 2.

Nothing had to be added up again.

4. What it costs

Building prefix is one pass over the data: O(n). After that, every range question is one subtraction: O(1). For q questions the whole thing costs O(n + q).

Memory is O(n) for the prefix array itself. You spend the space of one copy of the data, and in return the questions get cheap.

The gain shows when there are many questions. Adding up each range by hand costs O(n) per question and O(n·q) in total. With prefix built once, each question costs the same small, fixed time. One dashboard slider is enough to see the difference.

5. Where this shows up

Time-series dashboards and monitoring summaries compute the total for any date range without reading the raw rows again. Running reports of revenue and usage work the same way. So does any analytics API where the same data is queried over many different ranges.

The two-dimensional version is called an "integral image". Image filters use it to get the sum of any rectangle in constant time. That speeds up blurring and the feature checks used in face detection. Same method, one more dimension.

Range sums from a prefix array

rangeSum(buildPrefix([3, 1, 4, 1, 5, 9]), 1, 4)

arr

prefix (prefix[i] = sum of the first i values)

Build prefix one slot longer than arr. prefix[0] is the sum of nothing, so it is 0.

1 / 10

Speed race

40 range sums over the same 40 numbers

Bars: the 40 values. The prefix lane first turns them into running totals. There are as many queries as values, here and in the size table.

One operation is one value read. Every frame, each lane does the same number of operations, so the slow one falls behind.

Loop over each range O(n·q)

0 operations

Prefix sums O(n + q)

0 operations

And with more numbers

Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.

n = 1,000

Loop over each range334.3K · 3.3 ms

Prefix sums3K · under 1 ms

n = 100,000

Loop over each range3.3B · 33 s

Prefix sums300K · 3 ms

n = 10,000,000

Loop over each range33.3T · 3.9 days

Prefix sums30M · 300 ms

Recognise it

Prefix sums

Say these words and it is this pattern

many sum-over-a-range queries
answer several range-sum questions on the same array
sum from index l to r
running total or cumulative sum

Looks similar, isn't

Sliding window (fixed size)
A window answers about one span that keeps moving. Prefix sums answer about any span you name.
Difference array
That is the mirror image: many range writes, one read at the end. Here it is many reads.
Fenwick tree / segment tree
A prefix array breaks the moment a value changes. A Fenwick tree pays log n to allow updates.
Hash set / map
A map has no notion of a range at all. Counting subarrays needs the running total beside it.

n up to 1e6 with many range queries gives O(n) setup. Each query then costs O(1), plus O(n) memory.

On LeetCode

Problems that ask for the sum of many ranges, or compare what lies left of an index with what lies right of it. Build the running totals once and answer each question with one subtraction.

303.Range Sum Query - Immutable (opens in a new tab)Easy
The lesson task as a class, building prefix in the constructor and subtracting in sumRange.
1480.Running Sum of 1d Array (opens in a new tab)Easy
The answer is the prefix array itself, without its leading 0.
724.Find Pivot Index (opens in a new tab)Easy
At each index compare the sum on the left with the total minus the left sum minus the number itself.
238.Product of Array Except Self (opens in a new tab)Medium
The same idea with products, one pass from the left and one from the right.

Your task (Tier 1)

Write the function rangeSum(nums, queries).

Answer many questions of the form "the sum from position l to position r" fast. Build a helper list of running totals once, then answer each question with one subtraction.

Input: nums, a list of numbers, and queries, a list of [l, r] pairs (start and end position). Example: [2, 4, 1, 3], [[1, 3]].
Return: one sum per query, the sum of nums from position l to position r.

Steps:

Build a helper list prefix. Start it with a 0. Then add each number to the last value: prefix[i] = prefix[i-1] + nums[i-1]. So prefix[i] is the sum of the first i numbers.
For each pair [l, r] in queries, the sum from l to r is prefix[r+1] - prefix[l]. Add it to the answer list.
Return the answer list. The starting 0 in prefix is what keeps every range correct.

Done when all tests pass:

[2, 4, 1, 3], [[1,3], [0,0], [0,3]] -> [8, 2, 10]
[5, 6, 7], [[1,1]] -> [6] (one position)
[4], [[0,0]] -> [4]
[], [] -> []
[1, 2, 3], [] -> [] (no queries)

Practice

rangeSum

rangeSum(nums, queries) -> number[]

export function rangeSum(nums, queries) {
  // Your code here. The task is described in the box above the editor.
}

Running as a guest

The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.

Create a free account Log in

Hint ladder

Stuck? Reveal one rung at a time, but try it yourself first.

PreviousA window that remembers what's inside it NextCounting the stretches that add up to k