# Prefix Sum Array

# Prefix Sum Array

A prefix sum array stores cumulative sums so that any range sum can be computed in constant time.

You use it when many range sum queries are performed on static data.

## Problem

Given an array $A$ of length $n$, support queries of the form:

$$
\sum_{i=l}^{r} A[i]
$$

where

$$
0 \le l \le r < n
$$

## Structure

Define a prefix array $P$ such that:

$$
P[i] = A[0] + A[1] + \dots + A[i]
$$

## Algorithm

Build the prefix array:

```id="prefix-build"
build_prefix(A):
    n = length(A)
    P[0] = A[0]
    for i from 1 to n - 1:
        P[i] = P[i - 1] + A[i]
    return P
```

Answer a range query:

```id="prefix-query"
range_sum(P, l, r):
    if l == 0:
        return P[r]
    return P[r] - P[l - 1]
```

## Example

Let

$$
A = [8, 3, 5, 1, 9]
$$

Compute:

$$
P = [8, 11, 16, 17, 26]
$$

Query sum from index $1$ to $3$:

$$
\sum_{i=1}^{3} A[i] = 3 + 5 + 1 = 9
$$

Using prefix sums:

$$
P[3] - P[0] = 17 - 8 = 9
$$

| step   | value |
| ------ | ----- |
| P[3]   | 17    |
| P[0]   | 8     |
| result | 9     |

## Correctness

Each prefix value $P[i]$ stores the sum of elements from index $0$ to $i$. Subtracting $P[l-1]$ removes the contribution of elements before index $l$, leaving exactly the sum over $[l, r]$.

## Complexity

| operation | time   |
| --------- | ------ |
| build     | $O(n)$ |
| query     | $O(1)$ |

Space usage:

$$
O(n)
$$

## When to Use

Prefix sums are appropriate when:

* the array does not change
* many range sum queries are required
* preprocessing time is acceptable

They are less suitable when:

* frequent updates occur
* memory must remain minimal

In those cases, use Fenwick trees or segment trees.

## Implementation

```python id="prefix-python"
def build_prefix(a):
    p = [0] * len(a)
    p[0] = a[0]
    for i in range(1, len(a)):
        p[i] = p[i - 1] + a[i]
    return p

def range_sum(p, l, r):
    if l == 0:
        return p[r]
    return p[r] - p[l - 1]
```

```go id="prefix-go"
func BuildPrefix(a []int) []int {
    n := len(a)
    p := make([]int, n)
    p[0] = a[0]
    for i := 1; i < n; i++ {
        p[i] = p[i-1] + a[i]
    }
    return p
}

func RangeSum(p []int, l, r int) int {
    if l == 0 {
        return p[r]
    }
    return p[r] - p[l-1]
}
```