# LU.3 Prefix Sum

> Precompute running totals once in O(n), then answer any range-sum query with one subtraction in O(1).

Chapter: Level Up: Problem Patterns · ~35 min · easy · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/prefix-sum

## Mental model

A **car odometer**. To know how far you drove between Adama and Hawassa, you don't add up every kilometre again. You subtract the odometer reading at Adama from the reading at Hawassa.

A **prefix sum** array is that odometer: `p[i]` = sum of the first i items.

```cpp
p[0] = 0;
p[i + 1] = p[i] + a[i];
sum(a[l..r]) = p[r + 1] - p[l];
```

Building it is **O(n)**, once. After that, any range sum is **O(1)**. That is the time/space trade-off from Chapter 2: spend O(n) memory to save repeated work.

> Built on arrays and time/space trade-offs (Ch1–2). Not on the exam.

## C++ code: prefix-sum.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> buildPrefix(const vector<int>& a) {
    vector<int> p(a.size() + 1, 0);                   // p[i] = sum of first i items
    for (int i = 0; i < (int)a.size(); i++) p[i + 1] = p[i] + a[i];
    return p;
}

int rangeSum(const vector<int>& p, int l, int r) {    // sum of a[l..r]
    return p[r + 1] - p[l];
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2};
    vector<int> p = buildPrefix(a);
    cout << "prefix: ";
    for (int x : p) cout << x << " ";
    cout << "\n";
    cout << "sum a[1..4] = " << rangeSum(p, 1, 4) << "\n";
    cout << "sum a[0..6] = " << rangeSum(p, 0, 6) << "\n";
    cout << "sum a[5..5] = " << rangeSum(p, 5, 5) << "\n";
}
```

Expected output:

```text
prefix: 0 3 4 8 9 14 23 25 
sum a[1..4] = 11
sum a[0..6] = 25
sum a[5..5] = 9
```

## Complexity

| Case | Cost |
| --- | --- |
| build | O(n) |
| each range query | O(1) |
| q queries without prefix sums | O(n·q) |

Space: O(n)

Using size n + 1 with `p[0] = 0` removes the special case for ranges that start at index 0.

## Videos

- [Prefix Sum in 4 minutes](https://youtu.be/yuws7YK0Yng) (AlgoMasterIO): The whole pattern in 4 minutes.
- [Subarray Sum Equals K: Prefix Sums](https://youtu.be/fFVZt-6sgyo) (NeetCode): NeetCode combines prefix sums with a hash map (Chapter 8) for Subarray Sum Equals K.

## Exam lens

Likely questions:

- Build the prefix array of a given array and compute a range sum.
- Why is `p` one longer than `a`?

Common mistakes:

- Writing `p[r] − p[l]`. With the n + 1 layout it is `p[r + 1] − p[l]`.
- Rebuilding the prefix array for every query.

## Quick check

1. a = `3 1 4 1 5`. p = ?
   A. `3 4 8 9 14`
   B. `0 3 4 8 9 14`
   C. `0 3 1 4 1 5`
   D. `14 11 10 6 5`
   Answer: B. p[0] = 0, then running totals.

2. With that p, sum(a[1..3]) = ?
   A. p[3] − p[1] = 5
   B. p[4] − p[1] = 6
   C. p[4] − p[0] = 9
   D. p[3] − p[0] = 8
   Answer: B. 9 − 3 = 6 = 1 + 4 + 1.

3. Range query cost after building?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n²)
   Answer: A. One subtraction.

## Practice

**Trace by hand.** a = `3 1 4 1 5 9 2`. Build p and compute sum(a[1..4]), sum(a[0..6]) and sum(a[5..5]).

Solution:

p = `0 3 4 8 9 14 23 25`
- a[1..4] = p[5] − p[1] = 14 − 3 = **11**
- a[0..6] = p[7] − p[0] = **25**
- a[5..5] = p[6] − p[5] = **9**


**Implement it.** Find the pivot index where the sum of the left side equals the sum of the right side.

Hint: Total = p[n]. At index i: left = p[i], right = total − p[i + 1].

**Problems:**

- [Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/) (easy). Hint: Build p in the constructor; sumRange is one subtraction.
- [Find Pivot Index](https://leetcode.com/problems/find-pivot-index/) (easy). Hint: Left sum vs total − left − a[i].
- [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) (medium). Hint: Count how many earlier prefix sums equal `current − k`, using an unordered_map.

## Mastery checklist

- [ ] I can build a prefix-sum array.
- [ ] I can answer a range sum in O(1).
- [ ] I can combine prefix sums with a hash map.