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:

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:

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

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]

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]
}