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]
- prefix = [0, 2, 6, 7, 12, 15].
- prefix[3 + 1] = 12 is 2 + 4 + 1 + 5. prefix[1] = 2 is just the 2 before the range.
- 12 − 2 = 10, and indeed 4 + 1 + 5 = 10.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
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
prefix
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 includedreturn prefix[j + 1] - prefix[i] prefix = build([2, 4, 1, 5, 3])print(range_sum(prefix, 1, 3)) # 10print(range_sum(prefix, 0, 4)) # 15: the whole arrayprint(range_sum(prefix, 2, 2)) # 1: a single itemStep 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.