Prefix, Suffix & Range Updates

Answer repeated range questions with prefix sums

This is an optional deeper lesson after Foundation: Arrays & Strings. You should be comfortable tracing loops, distinguishing input positions from values, and reasoning about O(n) scans. Here we specialize in cumulative summaries: first queries, then excluding an element, then batched updates. Each range [l, r] is inclusive. Complexity uses the usual machine-word model.

Worked Trace: From Scanning to Prefix Sums

Take nums = [2, 1, 4, 3] and two questions, sum(1, 3) and sum(0, 2), where indices are inclusive at both ends. Scanning the first: 1 + 4 + 3 = 8. Scanning the second: 2 + 1 + 4 = 7. Six element touches for two queries on a four-element array — cheap now, ruinous at scale.

The insight is that those two scans repeat almost identical additions. If we store every running total once, each query becomes a subtraction. Build the prefix array, where prefix[k] is the sum of the first k elements — so prefix[0] = 0 by definition:

prefix[0] = 0
   ↓
prefix[1] = prefix[0] + nums[0] = 0 + 2 = 2
   ↓
prefix[2] = prefix[1] + nums[1] = 2 + 1 = 3
   ↓
prefix[3] = prefix[2] + nums[2] = 3 + 4 = 7
   ↓
prefix[4] = prefix[3] + nums[3] = 7 + 3 = 10

So prefix = [0, 2, 3, 7, 10], and the two answers are now single subtractions:

• sum(1, 3) = prefix[4] - prefix[1] = 10 − 2 = 8
• sum(0, 2) = prefix[3] - prefix[0] = 7 − 0 = 7

Why it works. prefix[r+1] is the sum of nums[0..r], and prefix[l] is the sum of nums[0..l-1]. Subtracting removes everything before l exactly, and what survives is nums[l..r]. The elements before l cancel; this cancellation idea is the seed of the difference-array trick we will meet in a later section, where it appears in a different guise.

Off-by-one is where this technique is won or lost. The four common cases:

The pattern is always prefix[r + 1] - prefix[l]. The extra +1 is not decoration: it exists because prefix is offset by one so that prefix[0] can represent the empty sum. Learners who drop it silently lose the last element of every range.

Guide Attempt: Predict Before You Check

Task. For nums = [5, 2, 8, 1, 9, 3] (six elements, inclusive ranges), predict all five answers — and write down the prefix array first, by hand, before computing anything. Prediction is the point here; the arithmetic confirms or corrects you.

1. sum(0, 5)
2. sum(2, 4)
3. sum(1, 1)
4. sum(3, 5)
5. sum(0, 0)

Independent Variation: Implement, Then Test Against Brute Force

Now write it. The build is one pass; the query is one subtraction.

def build_prefix(nums):
    # prefix[k] = sum of the first k elements; prefix[0] = 0 always
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix


def range_sum(prefix, l, r):
    # inclusive range [l, r]; the +1 on r is the whole ball game
    return prefix[r + 1] - prefix[l]


def brute(nums, l, r):
    return sum(nums[l:r + 1])

The safest habit is a randomized differential test: run both implementations on hundreds of small random arrays and every possible [l, r]. The direct sum is a simple reference to inspect, so a disagreement gives you a small case to debug in both implementations — and the assertion prints the offending indices for you.

import random

random.seed(0)  # reproducible failures

for _ in range(200):
    n = random.randint(1, 8)
    nums = [random.randint(-9, 9) for _ in range(n)]
    prefix = build_prefix(nums)
    for l in range(n):
        for r in range(l, n):
            got = range_sum(prefix, l, r)
            want = brute(nums, l, r)
            assert got == want, (nums, l, r, got, want)

print('all range sums match brute force')

The assertion fires with the array and the exact (l, r) that failed if anything is off; otherwise the script finishes quietly with the confirmation. Negative values are included deliberately — prefix sums never assume positivity, and a version that only works on non-negatives is a version that will fail in review. A neat aside: Python 3.8 and later can build the same array as list(accumulate(nums, initial=0)) using itertools.accumulate, which is worth knowing but not worth depending on if you want to see the indexing clearly.

Complexity. O(n) time and O(n) extra space to build; O(1) per query afterwards. A direct scan uses O(1) auxiliary space and O(k) time per query. The short brute above creates a k-element slice, so that particular reference also uses O(k) temporary space.

The catch, and it is a real one: prefix sums are a static-array tool. They assume the values never change between queries. The moment updates and queries interleave, a changed value invalidates every later prefix — which is exactly the gap the difference array closes for batch range updates, and the reason frequent online updates plus queries may justify a Fenwick or segment tree; occasional updates can simply rebuild the prefix array. For now, note the precondition and move on.

Check yourself before leaving this section:

• Can you state prefix[r + 1] - prefix[l] without looking, and explain the +1?
• Does your build produce prefix[0] = 0 and length n + 1?
• Does your differential test cover single-element ranges, full ranges, and negative values?
• Can you say why the build is O(n) and each query O(1)?

Reading the code above is not the same as having written and tested it. Type it, break the +1, watch the assert fire with the failing range, then fix it — that failure is the one you are most likely to repeat under time pressure.

Prefix and Suffix Decomposition: Excluding Elements, Pivot Points, and Balanced Splits

Hand someone nums = [1, 2, 3, 4] and ask for an array whose position i holds the product of every element except nums[i]. The obvious loop multiplies the other n - 1 values for each i — n² multiplications overall, and at n = 10⁵ (a size where quadratic work becomes substantial) that is on the order of 10¹⁰ operations. The question, though, gives its shape away: position i depends only on everything before i and everything after i, and those two groups never overlap. Summarize each group once, then combine.

The shape: "everything but me"

Call the left summary L[i] and the right summary R[i]. Build L in a prefix pass left to right; build R in a suffix pass right to left. Each pass is one linear scan, so the whole answer costs O(n) time. The combination step is whatever the problem asks for: multiply, add, take a minimum.

Notice the boundary values: L[0] = 1 and R[n-1] = 1. That is the identity element for the operation — the value that makes an empty group contribute nothing. For addition the identity is 0; for a maximum you need a sentinel such as −∞, or a rule for the missing side.

⚠️ Order matters in the loop. Write the answer for i before folding nums[i] into the running value. If you update first, nums[i] leaks into its own answer.

Worked example: product except self

def product_except_self(nums):
    n = len(nums)
    res = [1] * n

    left = 1
    for i in range(n):        # res[i] = product of nums[0 .. i-1]
        res[i] = left         # write first...
        left *= nums[i]       # ...then fold nums[i] in

    right = 1
    for i in range(n - 1, -1, -1):   # multiply in nums[i+1 .. n-1]
        res[i] *= right
        right *= nums[i]

    return res

Trace on [1, 2, 3, 4]. The left pass turns res into [1, 1, 2, 6]. The right pass walks backward: at i = 3, res[3] = 6 · 1 = 6, then right = 4; at i = 2, res[2] = 2 · 4 = 8, right = 12; at i = 1, res[1] = 1 · 12 = 12, right = 24; at i = 0, res[0] = 1 · 24 = 24. Result: [24, 12, 8, 6]. One output array and two scalar running values — O(n) time, O(1) extra space beyond the output.

⚠️ The tempting shortcut is to compute the total product once and divide by nums[i]. It collapses on [0, 1, 2]: the total is 0, and dividing at the zero's own index raises ZeroDivisionError. The running-product version has no such problem — it produces [2, 0, 0] with no special case.

Why [0, 1, 2] gives [2, 0, 0]: with one zero, every position other than the zero's own includes that zero among its factors and is therefore 0, while the zero's own position is the product of the rest, 1 · 2 = 2. With two or more zeros, every position contains some zero, so the whole output is 0. Both fall out of the passes without a single branch — a good sign you picked the right decomposition.

Attempt 1: the pivot index

A pivot index is an index where the sum of everything strictly left equals the sum of everything strictly right. Return the leftmost one, or -1.

Work these by hand before reading on: [1, 7, 3, 6, 5, 6], then [2, 1, -1], then [1, 2, 3].

You never need a full suffix-sum array here. One scalar — the total sum — plus the running prefix determines the suffix: right(i) = total - left(i) - nums[i]. The total is a sufficient statistic for "everything after," so a second array would be wasted space.

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        # right sum = total - left - x; check before folding x in
        if left == total - left - x:
            return i
        left += x
    return -1

Attempt 2 (harder): balanced split

Now change the constraint. Given an array of positive integers, decide whether it can be cut into two non-empty contiguous parts with equal sums. Return True or False.

Test yourself on [1, 2, 3, 6], [1, 3, 5, 7], and [3, 1, 1, 2].

Because prefix[k] + suffix = total, the two parts are equal exactly when prefix[k] == total / 2, so a single prefix scan settles the question in O(n) time.

def can_split(nums):
    total = sum(nums)
    if total % 2:                  # odd total: impossible
        return False
    half = total // 2
    prefix = 0
    n = len(nums)
    for i in range(n - 1):         # the last element must stay on the right
        prefix += nums[i]
        if prefix == half:
            return True
    return False

Two details. The loop stops at n - 1 so both parts are non-empty; matching half any earlier guarantees the leftover is non-empty too. And iterating range(n - 1) avoids nums[:-1], which would silently copy the list — a real cost at n = 10⁵. With positive integers the prefix sums strictly increase, so you could stop early once prefix > half; if the input allowed negatives that shortcut dies, because prefix sums are no longer monotone (the half check itself still stands).

Independent transfer

You are given heights h = [2, 1, 3, 1, 2]. For each index i, let left[i] be the tallest height strictly to the left of i and right[i] the tallest strictly to the right. A cell's water level is min(left[i], right[i]) when both sides exist and 0 otherwise; report the total water trapped above the bars (level - h[i], never below 0).

Work it out, then check.

That task is the skeleton of the classic trapping-rain-water problem — it is an optional application here, included to help you recognize the shape of the decomposition rather than one specific operation.

Quick self-check

Audit your own solution against these before moving on:

Next, the difference array turns this same "running summary" idea into constant-time range updates rather than just queries.

Difference Arrays: O(1) Range Updates and Prefix Reconstruction

You're given n flights numbered 0 to n-1 and a list of bookings. Each booking (first, last, seats) adds seats to every flight in that inclusive range. After all bookings, report the seat count on every flight.

The direct approach is honest but slow: for each booking, loop from first to last and add. If all m bookings span most of the n flights, that is O(n·m) work. With n = m = 10^5 that's on the order of 10^10 additions — far past what a typical judge tolerates.

The fix is a change of representation. Instead of storing the seat counts, store only where the count changes. Adding v to [l, r] changes nothing outside that range, so record two events: +v at l and -v at r+1. That structure is a difference array: diff[i] holds the signed change that begins at index i.

Why prefix-summing the diff reconstructs the values

Take a single event pair (+v at l, -v at r+1) and ask what a prefix sum through index i sees:

• If i < l: neither event is included → contribution 0.
• If l ≤ i ≤ r: the +v is included, the -v is not → contribution +v.
• If i ≥ r+1: both are included → +v - v = 0.

So each pair behaves like a switch that turns on at l and off at r+1. Events from different operations simply add, which is exactly why overlapping ranges need no special handling. The prefix sum never has to reason about operations individually — interior boundaries cancel, and only the start and end events survive.

That is the whole idea: O(1) per update, one O(n) prefix pass to materialize.

Worked trace

Start with zeros of length 5. We allocate diff with length 6 so the r+1 slot exists even when r = n-1.

idx   :   0   1   2   3   4   5
diffA :   0  +2   0   0  -2   0     after (l=1, r=3, +2)
diffB :   0  +2  +3   0  -2  -3     after (l=2, r=4, +3)
pref  :   0   2   5   5   3   -     running sum of diffB
value :   0   2   5   5   3   -     first n entries

Step by step:

1. Apply (1, 3, +2): diff[1] += 2 and diff[4] -= 2 → [0, 2, 0, 0, -2, 0].
2. Apply (2, 4, +3): diff[2] += 3 and diff[5] -= 3 → [0, 2, 3, 0, -2, -3].
3. Prefix sum: 0 → 2 → 5 → 5 → 3. The trailing -3 sits in slot 5 and is never read.

Spot-check index 3: operation 1 covers it (+2), operation 2 covers it (+3), total 5. ✓ Index 0 is covered by neither → 0. ✓ Index 4 is covered only by operation 2 → 3. ✓

This is exactly the shape of the classic flight-booking family of problems (often titled Range Addition and Corporate Flight Bookings): each booking is a range add, and the answer is the reconstructed array.

Implementation, and how it compares with the naive loop

def range_adds(n, ops):
    """Apply every (l, r, v) range add; return the final array."""
    diff = [0] * (n + 1)          # extra slot guards r + 1 when r == n - 1
    for l, r, v in ops:
        diff[l] += v
        diff[r + 1] -= v          # safe: index n exists
    result = []
    run = 0
    for i in range(n):            # one prefix pass; ignore diff[n]
        run += diff[i]
        result.append(run)
    return result

print(range_adds(5, [(1, 3, 2), (2, 4, 3)]))   # [0, 2, 5, 5, 3]

Contrast with the naive nested loop:

def range_adds_naive(n, ops):
    arr = [0] * n
    for l, r, v in ops:
        for i in range(l, r + 1):   # touches every element in the range
            arr[i] += v
    return arr

The reconstruction pass is the same prefix-sum machinery from the range-sum section — we've just chosen a clever array to run it on.

Edge cases, and where the trick stops working

⚠️ The r+1 boundary. If diff has length n, then diff[r+1] raises IndexError whenever r == n-1. Allocate n+1 and never read the last slot. The useful consequence: a full-range update [0, n-1] writes +v at index 0 and -v into the guard slot, so two boundary writes record the update; the O(n) reconstruction then applies it everywhere.

• l == 0: no special case — just diff[0] += v.
• l == r: a single-element add — +v, then -v one slot later.
• Negative v: works identically; values may go negative.
• Overlapping or nested ranges: purely additive, order-independent.

⚠️ The real limitation is online interleaving. This is a batch tool: apply every update, then materialize once. If a problem forces a query between updates — answer now, more updates still coming — the prefix reconstruction is stale the instant the next update lands, and rebuilding is O(n) per query. Frequent interleaving may justify an appropriately configured Fenwick tree or a segment tree with lazy propagation; occasional queries can still reconstruct the array, depending on the update/query workload.

Your turn

Task. Write range_add_materialize(n, ops) using the difference array. Then verify it against range_adds_naive on small random cases, and add explicit tests for: (a) l=0, r=n-1; (b) l == r; (c) two overlapping ranges; (d) a negative update. Predict each expected output before running.

import random

def range_add_materialize(n, ops):
    diff = [0] * (n + 1)
    for l, r, v in ops:
        diff[l] += v
        diff[r + 1] -= v
    out = [0] * n
    run = 0
    for i in range(n):
        run += diff[i]
        out[i] = run
    return out

## (a) full range
print(range_add_materialize(4, [(0, 3, 5)]))       # [5, 5, 5, 5]
## (b) single element
print(range_add_materialize(4, [(2, 2, 7)]))       # [0, 0, 7, 0]
## (c) overlapping
print(range_add_materialize(5, [(0, 2, 1), (1, 4, 2)]))   # [1, 3, 3, 2, 2]
## (d) negative
print(range_add_materialize(3, [(0, 1, -4)]))      # [-4, -4, 0]

## randomized cross-check against the naive simulator
for _ in range(1000):
    n = random.randint(1, 8)
    ops = []
    for _ in range(random.randint(0, 6)):
        l = random.randint(0, n - 1)
        r = random.randint(l, n - 1)
        ops.append((l, r, random.randint(-5, 5)))
    assert range_add_materialize(n, ops) == range_adds_naive(n, ops)
print("all matched")

Harder variation. After materializing, answer q range-sum queries on the final array without rescanning each time. Build a prefix-sum array over the result — pairing the prefix array from the range-sum section with the difference array here gives O(n + m + q) overall. Notice the duality: difference arrays make updates cheap; prefix arrays make queries cheap. The final task below uses exactly this combination.

Apply the combination: batch bookings, then range totals

You receive all range-add bookings first. After they have been applied, you must answer several totals over contiguous groups of flights. The input order gives you an opportunity: materialize the final counts once, then summarize those counts for queries. There is no need to change or rearrange the final array.

Try it before reading the solution. Use n = 5, bookings [(1,3,2), (2,4,3)], and queries [(0,4), (1,2), (4,4)]. Return the final counts and the three query answers. Explain why you need two cumulative passes over two different representations.

def booking_totals(n, bookings, queries):
    values = range_adds(n, bookings)
    prefix = build_prefix(values)
    answers = [range_sum(prefix, l, r) for l, r in queries]
    return values, answers

Extension: a non-zero starting array

If counts already exist in base, the difference-array pass computes the additions, not the entire result. First compute added = range_adds(len(base), bookings), then values = [base[i] + added[i] for i in range(len(base))]. Build the range-sum prefix over these combined values. The extra pass remains O(n).

For base = [2,0,5,1] and additions [(0,1,3),(2,3,2)], the added amounts are [3,3,2,2], so final values are [5,3,7,3]. Inclusive sums [0,3] and [1,2] are 18 and 10. Building the prefix before incorporating the additions would silently answer questions about the old values.

Verify meaning and boundaries

Use a direct simulator to apply every booking to every covered position on small inputs. Compare both the full materialized array and every query answer. Include a last-element update, a full-range update, overlapping updates, a negative adjustment and no updates. An empty bookings list with n > 0 still produces n zeroes; that is why initialization remains O(n). Queries here require valid non-empty inclusive ranges.

Changed constraint: if many point assignments and range-sum queries interleave, rebuilding the ordinary prefix table after every assignment can become expensive. A Fenwick tree supports point changes and range sums in O(log n), while range additions plus range sums require an appropriate variant, such as two Fenwick trees or a lazy segment tree. Those are further topics, not prerequisites for this batch solution. Occasional intermediate queries can still be answered correctly by reconstructing; correctness and efficiency are separate questions.

Before leaving, explain the distinction without code: a prefix table makes repeated sum queries cheap; prefix/suffix decomposition combines independent sides around an excluded position; a difference array makes recording batch additions cheap. Choose from the required operation and timing, not from the fact that all three use arrays.