Prefix and suffix arrays

A range question asked once is a loop. Asked ten thousand times, it is a data structure problem: the second query re-walks almost exactly the elements the first one walked. Precomputing every prefix once turns each of those queries into a single subtraction.

The same two passes — one forward, one backward — also answer questions about "everything except position i" without the division that looks obvious and is wrong.

The cost of asking twice

Sum the elements from index l to r, inclusive, q times:

def range_sum_slow(a, l, r):
    return sum(a[l:r + 1])          # O(r - l + 1), and it allocates a copy

With n = 10⁵ and q = 10⁵ queries, worst case each query walks the whole array: 10⁵ × 10⁵ = 10¹⁰ additions, about two minutes at roughly 10⁸ simple operations per second. The constraint table says a problem with those bounds wants something near O(n + q).

The waste is that query two re-adds the elements query one already added. So add them once, in order, and keep every running total.

The array with the extra slot

The version that looks natural stores the sum up to and including each index:

# The version that will cost you a bug
prefix = list(a)
for i in range(1, len(a)):
    prefix[i] += prefix[i - 1]      # prefix[i] = sum of a[0..i]

def range_sum(l, r):
    if l == 0:                      # the special case that always appears
        return prefix[r]
    return prefix[r] - prefix[l - 1]

That if is the tell. Define the array one slot longer instead, with a leading zero, and let prefix[i] mean the sum of the first i elements — so prefix[0] is the sum of no elements, which is 0:

prefix = [0] * (len(a) + 1)
for i, x in enumerate(a):
    prefix[i + 1] = prefix[i] + x   # prefix[i] = sum of the first i elements

def range_sum(l, r):                # inclusive on both ends
    return prefix[r + 1] - prefix[l]

The branch is gone, and no l = 0 case is left to forget. The empty range written the way it actually arises — r = l - 1, a loop that ran zero times — falls out for free as prefix[l] - prefix[l] = 0. Indices crossed any further are not empty ranges, they are caller bugs: l = 4, r = 0 evaluates prefix[1] - prefix[4] = 2 - 14 = -12, so validate at the call site rather than trusting the formula to notice. The reason the formula works is worth carrying: with the leading zero, prefix[i] sits on the boundary before a[i] rather than on the element itself, and a range is the gap between two boundaries.

An array of five values above a prefix array of six, whose cells line up with the boundaries between elements rather than with the elements themselves100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

With a = [2, 4, 1, 7, 3] the prefix array is [0, 2, 6, 7, 14, 17], and sum(a[1..3]) = prefix[4] − prefix[1] = 14 − 2 = 12, which is 4 + 1 + 7. The build is n additions, each query is one subtraction: 10⁵ + 10⁵ = 2 × 10⁵ operations against 10¹⁰, a factor of fifty thousand.

Two sides: everything except me

Now the two-sided question. Return an array where out[i] is the product of every element except a[i].

The division answer arrives immediately: multiply everything, then divide by a[i]. It is wrong, and it is wrong for a reason worth stating precisely — a single zero. With a = [2, 0, 3] the total product is 0, so total // a[i] gives 0 at every index it does not crash on — and at index 1 it divides by zero — while the true answer there is 2 × 3 = 6. With two zeros every position is 0; with exactly one, exactly one position is not. Counting the zeros to special-case it works, and is three branches of bookkeeping. Modular arithmetic has no division at all without an inverse, which needs a prime modulus and a non-zero value.

Split the product instead. Everything except a[i] is everything to its left times everything to its right, and both of those are cumulative:

def product_except_self(a):
    n = len(a)
    out = [1] * n

    running = 1                     # product of a[0..i-1]
    for i in range(n):
        out[i] = running
        running *= a[i]

    running = 1                     # product of a[i+1..n-1]
    for i in range(n - 1, -1, -1):
        out[i] *= running
        running *= a[i]

    return out

On a = [2, 4, 1, 7, 3] the forward pass leaves [1, 2, 8, 8, 56] and the backward pass multiplies in [84, 21, 21, 3, 1], giving [84, 42, 168, 24, 56]. Check the middle: 2 × 4 × 7 × 3 = 168, and no element was divided by anything. Two passes, O(n) time, and the output array is the only allocation.

Note the same read-then-extend order as in one pass with state: out[i] is written from running before a[i] is folded in, because running must mean "strictly to the left".

Which operations this works for

Any associative operation can be accumulated forward and backward, so the two-sided trick — combine everything left of i with everything right of i — works for maximum, minimum, gcd, xor, and counts. "The maximum of the array with a[i] removed" is a prefix-max pass and a suffix-max pass, nothing more.

The range form is stricter. prefix[r+1] ⊖ prefix[l] needs an operation you can undo:

Operation	Range query by subtraction?	Why
sum	yes	subtract
xor	yes	xor is its own inverse
count of items matching a test	yes	counts subtract
product	only if no element is 0	division, and the zero case
max, min, gcd	no	nothing to cancel with

Counting is the one people under-use. A prefix array of "how many even numbers so far" answers "how many evens in a[l..r]" as c[r+1] − c[l], and the same shape counts vowels, elements above a threshold, or days that hit a target.

For range max or gcd — associative but not invertible — the prefix idea does not apply, and you need a sparse table or a segment tree instead.

In an interview

Lead with the boundary definition: "I will make the prefix array n + 1 long, with prefix[i] the sum of the first i elements, so prefix[0] = 0." That one sentence pre-empts the off-by-one the interviewer is waiting for, and it makes the query formula obvious rather than remembered.

For product-except-self, say why division is out before you are asked. "Division breaks on a zero, and there is no division in a modular version, so I will use a prefix pass and a suffix pass." Then, if the follow-up is "O(1) extra space", you already have it: write the prefix pass into the output array and fold the suffix in on the way back.

The mistake that loses points: building the prefix array and then still looping inside the query, or writing prefix[r] - prefix[l] — forgetting the + 1 on r, which silently drops the last element of the range. With a = [2, 4, 1, 7, 3], l = 1 and r = 3, that gives prefix[3] - prefix[1] = 7 − 2 = 5 against the true 12, short by exactly a[3] = 7. Test l = r — a single element — and l = 0 before you claim it works, the way the solving loop asks.

Check yourself

a = [2, 4, 1, 7, 3]. Write the prefix array with the leading zero, then get the sum of a[2..4] from it.

[0, 2, 6, 7, 14, 17]. The sum is prefix[5] − prefix[2] = 17 − 6 = 11, which is 1 + 7 + 3.

q = 10⁵ range-sum queries on n = 10⁵ elements. Compare the two approaches in operations.

Re-summing each query is up to 10⁵ × 10⁵ = 10¹⁰ additions, about two minutes. Prefix sums cost 10⁵ to build plus 10⁵ subtractions, so 2 × 10⁵ — the build is paid once and every query is O(1).

Someone proposes prefix maxima so that "the maximum of a[l..r] is prefix_max[r+1] minus prefix_max[l]". What do you say?

Maximum has no inverse, so there is nothing to subtract — the prefix maximum over a[0..r] may come from an element left of l. Prefix and suffix maxima do answer "maximum excluding index i", but arbitrary ranges need a sparse table or a segment tree.