Overview
EasyPrecompute running totals · range sum in O(1)
Add up numbers as you go, so any range total becomes just one subtraction later.
The idea
Build an array where P[i] is the sum of everything before i. Then the sum of any range [l, r] is just P[r+1] − P[l] — no re-adding required.
3
1
4
1
5
0
1
2
3
4
Step 1 of 8. A prefix sum is just a running total. Add each number to the total so far. Values: 3, 1, 4, 1, 5.
1/8
Optimal
timeO(n) build, O(1) queryspaceO(n)
One subtraction per range.
1const P = [0];2for (let i = 0; i < n; i++) P.push(P[i] + nums[i]);3const rangeSum = (l, r) => P[r + 1] - P[l];Input
- array
- [3, 1, 4, 1, 5]
Memory
- running total
- —
- total@4
- —
- total@1
- —
Output
- range sum
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 4, 1, 3], sum of nums[1..2]
- Output:
- 5
- Explanation:
- Prefix sums are [0, 2, 6, 7, 10]. The answer is prefix[3] - prefix[1] = 7 - 2, one subtraction instead of a loop.
Example 2
- Input:
- 1000 range queries on the same array
- Output:
- one O(n) pass, then O(1) each
- Explanation:
- Paying once up front is what makes the queries free. That trade is the whole pattern.
Finished the walkthrough? Add it to your streak.