Prefix Sum (Range Sum Query) Algorithm Tutorial

Prefix Sum

Prefix Sum, also known as cumulative sum or running total, preprocesses an array so you can answer range sum queries in $O(1)$ time after $O(n)$ preprocessing.

You define $prefix[i]$ as the sum of elements from index $0$ to $i-1$. The sum from $L$ to $R$ is $prefix[R+1] - prefix[L]$.

function buildPrefixSum(arr, n):
    prefix = array of size n + 1
    prefix[0] = 0
    for i from 0 to n - 1:
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

function rangeSum(prefix, L, R):
    return prefix[R + 1] - prefix[L]

Why $prefix[0] = 0$: This handles the edge case when $L = 0$. The sum from $0$ to $R$ is just $prefix[R+1] - prefix[0] = prefix[R+1]$.

2D prefix sum: For a matrix, you use $prefix[i][j]$ representing the sum of the rectangle from $(0,0)$ to $(i-1,j-1)$. You apply inclusion-exclusion for rectangle queries.

When to use what: Use prefix sums when your array is static. Use Segment Trees when you need both queries and updates.

Applications: You use Prefix Sum for range sum queries, subarray sum problems, 2D region queries, and difference arrays for range updates.

Time complexity: $O(n)$ preprocessing, $O(1)$ per query.

Space complexity: $O(n)$ for the prefix array.