Prefix Sums: Range-Sum Queries in O(1)

A prefix sum array stores the running total of an array, so prefix[i] is the sum of the first i elements. With it built once in O(n), the sum of any contiguous range answers in O(1) — a simple subtraction — instead of re-adding the range every time.

The idea

Define prefix[0] = 0 and prefix[i] = a[0] + a[1] + ... + a[i-1]. That one-slot offset (a leading zero) makes the math clean: the sum of a[l..r] (inclusive) is

sum(l..r) = prefix[r + 1] - prefix[l]

Why it works: prefix[r+1] is everything up to and including r; subtracting prefix[l] removes everything before l, leaving exactly a[l..r].

Building and querying

#include <vector>
struct RangeSum {
    std::vector<long long> prefix;        // size n + 1, prefix[0] = 0
    RangeSum(const std::vector<int>& a) : prefix(a.size() + 1, 0) {
        for (int i = 0; i < (int)a.size(); i++)
            prefix[i + 1] = prefix[i] + a[i];
    }
    long long query(int l, int r) {       // inclusive a[l..r]
        return prefix[r + 1] - prefix[l];
    }
};

class RangeSum {
    long[] prefix;                        // size n + 1, prefix[0] = 0
    RangeSum(int[] a) {
        prefix = new long[a.length + 1];
        for (int i = 0; i < a.length; i++)
            prefix[i + 1] = prefix[i] + a[i];
    }
    long query(int l, int r) {            // inclusive a[l..r]
        return prefix[r + 1] - prefix[l];
    }
}

class RangeSum {
  constructor(a) {
    this.prefix = new Array(a.length + 1).fill(0); // prefix[0] = 0
    for (let i = 0; i < a.length; i++)
      this.prefix[i + 1] = this.prefix[i] + a[i];
  }
  query(l, r) {                           // inclusive a[l..r]
    return this.prefix[r + 1] - this.prefix[l];
  }
}

class RangeSum:
    def __init__(self, a):
        self.prefix = [0] * (len(a) + 1)  # prefix[0] = 0
        for i in range(len(a)):
            self.prefix[i + 1] = self.prefix[i] + a[i]

    def query(self, l, r):                # inclusive a[l..r]
        return self.prefix[r + 1] - self.prefix[l]

Tracing it

For a = [3, 1, 4, 1, 5]:

index    0  1  2  3  4  5
prefix   0  3  4  8  9  14
sum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 6   (1 + 4 + 1)
sum(0..4) = prefix[5] - prefix[0] = 14 - 0 = 14 (whole array)

Complexity

• Build: O(n) time, O(n) space.
• Each query: O(1) time.

This is the classic trade: spend O(n) memory and a single pass up front to make every subsequent range query free. It pays off the moment you have more than a couple of queries.

For beginners: The leading zero is the whole trick. Without it you need an awkward special case for l == 0. With prefix[0] = 0 and a size n + 1 array, the formula prefix[r+1] - prefix[l] always works, including for ranges that start at index 0.

Prefix sum vs sliding window

They solve overlapping problems but differ in shape:

• A sliding window sweeps a contiguous region forward and is ideal when the window moves monotonically.
• A prefix sum answers arbitrary, out-of-order range queries in O(1) and shines when ranges jump around or when combined with a hash map (see prefix sum applications).

Common pitfalls

• Off-by-one. Decide inclusive vs exclusive ranges once and stick to it. With the leading-zero convention, inclusive a[l..r] is prefix[r+1] - prefix[l].
• Mutating the array after building. Prefix sums are a snapshot; if a changes you must rebuild (or switch to a Fenwick tree for fast updates).
• Overflow. Cumulative sums grow large fast — use a 64-bit accumulator.

Going deeper: The same precompute-then-subtract idea extends to 2D grids (sum of any submatrix in O(1)), prefix XOR, and prefix products. The 2D version and the hash-map trick are covered next.

Next: put prefix sums to work in prefix sum applications, or practice on the exercises.