Know this before you start: “A range sum is prefix[j + 1] − prefix[i]”

Any range sum in one subtraction

The sum of nums[i..j] is everything up to j minus everything before i: prefix[j + 1] − prefix[i]. per question after one pass.

The idea

prefix[j + 1] adds up nums[0] … nums[j]. prefix[i] adds up nums[0] … nums[i − 1]. Subtract them and the shared start cancels, leaving exactly nums[i] … nums[j].

That's why the extra 0 at the front matters: a range starting at i = 0 is prefix[j + 1] − prefix[0] = prefix[j + 1], no special case.

It pays off when there are many questions about one array. Adding each range from scratch costs O(length) per question; with each one costs O(1).

Worked example

Sum of nums[1..3] in [2, 4, 1, 5, 3]

  1. prefix = [0, 2, 6, 7, 12, 15].
  2. prefix[3 + 1] = 12 is 2 + 4 + 1 + 5. prefix[1] = 2 is just the 2 before the range.
  3. 12 − 2 = 10, and indeed 4 + 1 + 5 = 10.

Pseudocode

The steps in plain words. ← means “set to”; indentation shows what's inside what.

build prefix once: prefix[0] ← 0, prefix[k + 1] ← prefix[k] + nums[k]
sum of nums[i..j] ← prefix[j + 1] − prefix[i]
(everything up to j, minus everything before i)

See it run

The worked example, step by step, beside the Python. The highlighted line is the one running.

Step-by-step

nums = [2, 4, 1, 5, 3], i = 1, j = 3

nums

02
14
21
35
43

prefix

00

Solution · Pythonline 2

def build(nums):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return prefix
def range_sum(prefix, i, j): # nums[i] + … + nums[j], both included
return prefix[j + 1] - prefix[i]
prefix = build([2, 4, 1, 5, 3])
print(range_sum(prefix, 1, 3)) # 10
print(range_sum(prefix, 0, 4)) # 15: the whole array
print(range_sum(prefix, 2, 2)) # 1: a single item

Step 1 of 4· line 2

Build the running totals once, starting from 0.

O(n) once to build, then O(1) per range: q questions cost O(n + q) instead of O(n · q).

When you'll use it

  • Many sum questions about one array that doesn't change.
  • Averages over a range, “sales between two dates”, and the 2D version for sums over a rectangle.

In the wild · Analytics dashboards: “Sales between March 3 and March 17” is one subtraction of two running totals, so charts answer any date range instantly instead of re-adding every day.

Common mistakes

  • prefix[j] − prefix[i], which drops nums[j]: the right end needs j + 1.
  • Using prefix sums when the array keeps changing: every update would shift all later totals.

Practise it · before the Prefix Sum problems

Answer every range sum

For each query [i, j], return nums[i] + … + nums[j] (both ends included). Return the answers in query order.

Input nums = [2, 4, 1, 5, 3], queries = [[1, 3], [0, 4], [2, 2]]

Output [10, 15, 1]

Input nums = [-1, 2], queries = [[0, 0], [0, 1]]

Output [-1, 1]

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?