What is a prefix sum, and how does it speed up range queries?

Question

Accepted Answer

A **prefix sum** array stores cumulative totals so any **range sum** can be answered in **O(1)** after O(n) preprocessing — instead of O(n) per query.

## The idea

Let `prefix[i]` be the sum of the first `i` elements. Then the sum of `arr[l..r]` is `prefix[r+1] - prefix[l]`.

## Example

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Trace

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Complexity

- **Build:** O(n). **Query:** O(1). **Space:** O(n).

## When to use / pitfalls

Ideal for **many range-sum queries** on static data. Variants: 2D prefix sums for submatrix sums, prefix XOR, and difference arrays for range updates. If the array changes often, use a Fenwick/segment tree instead. Watch the index offset (size n+1).

## Why it matters

Prefix sums turn repeated O(n) range queries into O(1) lookups — a huge win when queries are frequent.

The precompute-once, answer-fast pattern generalizes to many data-processing tasks.

It is a staple of competitive programming and a common building block in analytics.