Prefix, Suffix & Range Updates

A range has only two ends

An airline runs 100,000 flights, numbered 0 to 99,999. Overnight, 100,000 group bookings arrive, each shaped like "add 3 seats to every flight from 20,000 to 90,000". In the morning, the finance team sends 100,000 questions shaped like "how many seats did we sell on flights l through r?"

The obvious plan adds each booking one flight at a time and answers each question by adding up its flights. A booking can cover all 100,000 flights, so the bookings alone can cost 100,000 × 100,000 = 10¹⁰ additions. The questions can cost as much again. A judge gives you a second or two.

Both halves waste effort the same way: they walk through the inside of a range, but only its two ends carry information. A booking raises every seat count in its range by the same amount, so compared with its neighbours the count only jumps in two places: where the booking starts and just after it stops. A question needs only the running total before l and the running total through r. Store cumulative information once, and every range update or range question touches two cells. That is this lesson in one sentence.

The boss level combines moves 4 and 1 to solve the airline.

This lesson builds on Foundation: Arrays & Strings, especially Move 1 (carry a running summary) and Move 6 (the prefix array and prefix[r + 1] − prefix[l]). Counting subarrays with a given sum, which pairs prefix sums with a hash map, belongs to Hash Maps & Sets. Structures that accept updates and queries in any order belong to Trees & Advanced Structures. Traces use zero-based indices, and a range [l, r] includes both ends unless a problem says otherwise.

Warm-up: two readings answer any range

Smell: the array never changes, and many questions ask for the sum of a stretch of it.

A quick recap of Foundation's Move 6. prefix[k] is the sum of the first k elements, so prefix[0] = 0 and the table has n + 1 entries. The readings sit between elements. An inclusive range [l, r] is the reading after r minus the reading before l:

from itertools import accumulate

def build_prefix(nums):
    return list(accumulate(nums, initial=0))   # prefix[k] = sum(nums[:k]); Python 3.8+

def range_sum(prefix, l, r):                   # inclusive, 0 <= l <= r < len(nums)
    return prefix[r + 1] - prefix[l]

prefix = build_prefix([2, 1, 4, 3])
print(prefix, range_sum(prefix, 1, 3))         # [0, 2, 3, 7, 10] 8

accumulate(..., initial=0) builds the same table as Foundation's explicit loop. Building it costs O(n) time and O(n) extra space, where n is the array length, and each query is O(1). Python integers never overflow. In Java or C++, 10⁵ values of up to 10⁵ each add up to 10¹⁰, so store the prefix in a 64-bit type.

Predict first: the trick needs a way to remove everything before l. For which of these can two readings of a prefix table answer any range? (a) the sum; (b) the XOR; (c) how many elements are even; (d) the product; (e) the maximum.

The table has one precondition: the values must not change between queries. Change nums[i] and every reading after position i is stale. If all the changes arrive before the first query, apply them first; the difference array later in this lesson does that cheaply. If changes and queries keep interleaving, you need a structure built for it, such as the Fenwick tree in Trees & Advanced Structures.

Your turn: LeetCode 2559: Count Vowel Strings in Ranges. You get up to 10⁵ words and up to 10⁵ queries [l, r]. For each query, count the words in that inclusive index range that start and end with a vowel. Predict the answers for words = ["aba", "bcb", "ece", "aa", "e"] and queries [[0, 2], [1, 4], [1, 1]], then write it in O(n + q) time, where n is the number of words and q the number of queries.

from itertools import accumulate

def vowel_strings(words, queries):
    vowels = set("aeiou")
    flags = [1 if w[0] in vowels and w[-1] in vowels else 0 for w in words]
    prefix = list(accumulate(flags, initial=0))
    return [prefix[r + 1] - prefix[l] for l, r in queries]

Everything but me: one pass from each end

Smell: for each position, the slow code loops over all the other positions.

LeetCode 238: Product of Array Except Self asks for an array answer where answer[i] is the product of every element except nums[i]. For [1, 2, 3, 4] the answer is [24, 12, 8, 6]. There are up to 10⁵ elements, the solution must run in O(n) time, and division is not allowed.

Predict first: the tempting shortcut ignores that last rule. Multiply everything once, then divide by nums[i]. What happens on [3, 0, 4], and what is the right answer?

The slow version multiplies the other n − 1 values at every index: about n² multiplications, around 10¹⁰ at n = 10⁵. Look at what it repeats. The answer at i splits into two groups that never overlap:

answer[i] = (nums[0] · … · nums[i-1])  ×  (nums[i+1] · … · nums[n-1])
              everything left of i          everything right of i

The left group for i + 1 is the left group for i times nums[i]. That is Foundation's running summary again, carried once from the left end and once from the right end.

You don't need two extra arrays. Store the left products in the output, then multiply the right products in on a backward pass:

def product_except_self(nums):
    n = len(nums)
    res = [1] * n
    left = 1                          # product of nums[0 .. i-1]
    for i in range(n):
        res[i] = left                 # write first...
        left *= nums[i]               # ...then fold nums[i] in
    right = 1                         # product of nums[i+1 .. n-1]
    for i in range(n - 1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

Trace on [1, 2, 3, 4]:

Why it works

There is one invariant per pass. Before the left pass handles i, left is the product of nums[0..i−1]. Before the right pass handles i, right is the product of nums[i+1..n−1]. The left pass stores the first factor in res[i], the right pass multiplies in the second, and nothing else touches res[i]. Zeros need no special case, because a zero simply sits in the groups it belongs to.

Two passes give O(n) time. The extra space is two integers, O(1), because LeetCode doesn't count the output array.

Two lines that decide correctness

The empty side is the identity. Nothing sits left of index 0, so left starts at 1, the value that leaves a product unchanged. For sums the identity is 0. Ordinary integers have no neutral value for a maximum, so you add one, -inf, which every number beats. Or you use whatever the problem says a missing side means. The next exercise starts its maximum at 0, which works because heights are never negative.

⚠️ Write, then fold. Swap the two lines in both loops and nums[i] leaks into its own answer. res[i] becomes the product of nums[0..i] times the product of nums[i..n−1], which is the total times nums[i], so [1, 2, 3, 4] returns [24, 48, 72, 96]. It is the same ordering rule as Foundation's seen set: check first, then add.

Your turn: LeetCode 42: Trapping Rain Water. Bars of width 1 have heights h, up to 2 × 10⁴ of them. After rain, water above bar i rises to the lower of two walls: the tallest bar on its left and the tallest bar on its right. So the bar holds min(tallest on the left, tallest on the right) − h[i] units, and never less than 0. Work out h = [2, 1, 3, 1, 2] by hand, then write it in O(n) time. Which summary does each pass carry, and how do you combine them?

def trap(height):
    n = len(height)
    left_max = [0] * n
    best = 0                          # identity for max here: heights are >= 0
    for i in range(n):
        best = max(best, height[i])
        left_max[i] = best            # tallest bar in height[0..i]
    right_max = [0] * n
    best = 0
    for i in range(n - 1, -1, -1):
        best = max(best, height[i])
        right_max[i] = best           # tallest bar in height[i..n-1]
    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

print(trap([2, 1, 3, 1, 2]), trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 2 6

Left against right: pivot index and balanced split

Smell: at every position, or at every cut, the slow code adds up the left side and the right side from scratch.

LeetCode 724: Find Pivot Index, which is the same problem as LeetCode 1991. A pivot index is an index where the sum of everything strictly to its left equals the sum of everything strictly to its right. An empty side sums to 0. Return the leftmost pivot, or −1 if there is none. There are up to 10⁴ elements, and values may be negative.

Predict first: find the pivot of [1, 7, 3, 6, 5, 6], of [2, 1, −1] and of [1, 2, 3] by hand.

The slow version computes sum(nums[:i]) and sum(nums[i + 1:]) for every i: O(n²) time, and every slice makes a copy. You could fix it the way product-except-self did, with a left pass and a right pass. But addition has an inverse, so there is a shortcut. Every element sits in exactly one of three places:

left + nums[i] + right = total

So the total, together with the running left sum, determines the right sum: right = total − left − nums[i]. One number replaces a whole suffix array.

def pivot_index(nums):
    total = sum(nums)
    left = 0                              # sum of nums[0 .. i-1]
    for i, x in enumerate(nums):
        if left == total - left - x:      # right side = total - left - x
            return i
        left += x                         # fold x in only after the check
    return -1

Trace on [1, 7, 3, 6, 5, 6], where the total is 28:

Why it works. Invariant: when the loop reaches i, left is the sum of nums[0..i−1]. The equation above then gives the exact right sum, so the check tests the definition of a pivot at every index, from left to right, and the first hit is the leftmost pivot. It takes O(n) time (one pass inside sum, one in the loop) and O(1) extra space.

Edge cases. Negative values are fine, because nothing here relies on sums growing. Both ends are real candidates: index 0 compares 0 with the rest, and index n − 1 compares the rest with 0. A one-element array always returns 0. And the order rule from the previous section applies again: fold x into left only after the check.

Your turn: cut instead of exclude

A pivot leaves out one element. Now every element must go to one side. Given an array of positive integers, can you cut it into two non-empty contiguous parts with equal sums? Try [1, 2, 3, 6], [1, 3, 5, 7] and [3, 1, 1, 2], then write it in O(n) time and O(1) extra space.

Then change the constraint: zeros and negative numbers are now allowed. Does your loop bound still matter? Try [3, −3] and [0].

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

Difference arrays: touch two cells, not the whole range

Smell: many operations each say "add v to every cell from l to r", and nobody reads the array until the operations are done.

Here is the hook's first half, 0-indexed. There are n flights numbered 0 to n − 1, all starting at 0 seats. Each booking (l, r, v) adds v seats to every flight from l to r inclusive. After all bookings, return the seat count of every flight. That is LeetCode 370: Range Addition, a premium problem. LeetCode 1109: Corporate Flight Bookings is the same task with flights numbered 1 to n.

The slow version is a 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 cell in the range
            arr[i] += v
    return arr

With m bookings that each cover most of the n flights, that is O(n · m) work: 10¹⁰ additions at n = m = 10⁵. Every booking walks through the inside of its range, where nothing interesting happens.

Predict first: start from [0, 0, 0, 0, 0] and add 2 to indices 1 through 3, which gives [0, 2, 2, 2, 0]. Now write down each cell minus the cell to its left, counting the cell left of index 0 as 0. How many of those differences are non-zero? Would that number change if the range covered 1,000 cells?

That is the whole trick. Store the differences instead of the values. A range add becomes two writes: +v at l and −v at r + 1. To get the values back, take a running sum of the differences. This array of differences is called a difference array: diff[i] holds the change that begins at index i.

def range_adds(n, ops):
    diff = [0] * (n + 1)              # slot n catches r + 1 when r == n - 1
    for l, r, v in ops:
        diff[l] += v                  # the change starts at l...
        diff[r + 1] -= v              # ...and is undone right after r
    values = []
    running = 0
    for i in range(n):                # a prefix sum over diff; slot n is never read
        running += diff[i]
        values.append(running)
    return values

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

Trace with n = 5 and the bookings (1, 3, +2) and (2, 4, +3):

index            0    1    2    3    4    5
after (1,3,+2)   0   +2    0    0   -2    0
after (2,4,+3)   0   +2   +3    0   -2   -3
running sum      0    2    5    5    3    -     <- the answer [0, 2, 5, 5, 3]

The −3 in slot 5 is never read. Spot-check index 3: both bookings cover it, and 2 + 3 = 5. Index 4 is covered only by the second booking, so it holds 3.

Why the running sum rebuilds the values

The running sum at index i adds up every change recorded at an index ≤ i. Take one booking's pair of changes, +v at l and −v at r + 1:

• If i < l, neither change is included, so the booking contributes 0.
• If l ≤ i ≤ r, only the +v is included, so it contributes v.
• If i > r, both are included, so it contributes v − v = 0.

Each booking acts like a switch that turns on at l and off at r + 1, and the switches of different bookings simply add. That is why overlapping and nested ranges need no special handling.

💡 Differences and prefix sums undo each other. Take the differences of any array and prefix-sum them, and you get the array back, because a[0] + (a[1] − a[0]) + (a[2] − a[1]) + … + (a[i] − a[i−1]) collapses to a[i]. (The first difference is a[0] itself, since the cell left of index 0 counts as 0.) Differences make updates cheap and prefix sums make queries cheap. The boss level uses both.

Where the boundary goes, and where the trick stops

⚠️ The r + 1 slot. With only n slots, diff[r + 1] raises IndexError whenever r = n − 1. Allocate n + 1 slots and never read the last one. A booking that covers every flight then writes +v at index 0 and −v into that spare slot.

• l = 0, l = r, negative v, overlapping ranges: no special cases needed.
• 1-indexed input, as in LeetCode 1109: subtract 1 from both ends before recording.
• Half-open ranges. Some problems say a range stops before its end point, like passengers who get off at stop to. Then the change stops at to: write −v at to, not at to + 1. Look for the word "inclusive" in the statement.
• Huge coordinates. If positions go up to 10⁹, you can't allocate diff. Keep the changes in a dictionary instead and walk its keys in sorted order: O(m log m) time and O(m) space for m ranges. This version is often called a sweep line.

⚠️ The real limit: all updates first. The running sum at i is final only after every booking has been recorded. If a problem makes you answer a query between updates, each answer costs an O(n) rebuild. That is fine for a handful of queries and hopeless for 10⁵ of them. There is one exception. If you read positions left to right and every new update starts after the positions you have already read, those readings stay final. For heavy interleaving, a Fenwick tree over diff supports range add and single-cell reads in O(log n) each. Range add together with range sums needs two Fenwick trees or a segment tree with lazy propagation. Trees & Advanced Structures introduces Fenwick and segment trees.

Your turn: LeetCode 1094: Car Pooling. A car with capacity seats drives east. Each trip [p, from, to] means p passengers board at kilometre from and get off at kilometre to. At the same point, passengers get off before new ones board. Can the car do every trip without ever holding more than capacity passengers? There are up to 1,000 trips, with 0 ≤ from < to ≤ 1000. Predict [[2, 1, 5], [3, 3, 7]] with capacity 4, then with capacity 5. Then predict the case that catches boundary bugs, [[2, 1, 5], [3, 5, 7]] with capacity 3. Write it in O(m + L) time, where m is the number of trips and L = 1,001 is the number of kilometre points.

def car_pooling(trips, capacity):
    diff = [0] * 1001                 # kilometres 0..1000
    for p, start, end in trips:
        diff[start] += p              # they board at start
        diff[end] -= p                # gone AT end: the range is half-open
    load = 0
    for change in diff:
        load += change
        if load > capacity:
            return False
    return True

import random

def car_pooling_brute(trips, capacity):
    return all(sum(p for p, s, e in trips if s <= km < e) <= capacity
               for km in range(1001))

for _ in range(1000):
    trips = []
    for _ in range(random.randint(1, 5)):
        s = random.randint(0, 12)
        trips.append([random.randint(1, 5), s, random.randint(s + 1, 14)])
    cap = random.randint(1, 12)
    assert car_pooling(trips, cap) == car_pooling_brute(trips, cap), (trips, cap)
print("all matched")

Boss level: bookings first, questions after

Back to the airline. All bookings arrive first, and then come many questions of the form "total seats on flights l through r". You now have both halves:

1. Changes → values: record every booking in a difference array, then take its running sum.
2. Values → totals: build a prefix table over those values, and answer each question with two readings.

Try it first: with n = 5, bookings [(1, 3, 2), (2, 4, 3)] and queries [(0, 4), (1, 2), (4, 4)], what are the three answers? And why can't a single running sum over diff answer the questions?

# uses range_adds (difference arrays) and build_prefix / range_sum (warm-up)
def booking_totals(n, bookings, queries):
    values = range_adds(n, bookings)       # pass 1: changes -> values
    prefix = build_prefix(values)          # pass 2: values -> running totals
    return values, [range_sum(prefix, l, r) for l, r in queries]

print(booking_totals(5, [(1, 3, 2), (2, 4, 3)], [(0, 4), (1, 2), (4, 4)]))
# ([0, 2, 5, 5, 3], [15, 7, 3])

index      0    1    2    3    4    5
diff       0   +2   +3    0   -2   -3
values     0    2    5    5    3          <- running sum of diff[0..4]
prefix     0    0    2    7   12   15     <- prefix[k] = sum of the first k values

For n flights, m bookings and q questions this is O(n + m + q) time. On the hook's numbers that is a few hundred thousand steps instead of up to 2 × 10¹⁰. The extra space is O(n) for diff, the values and the prefix table, plus O(q) for the answers.

⚠️ Build the prefix table after the last booking. A table built earlier describes the old seat counts. Every query then returns a plausible number about the wrong array, and nothing crashes to warn you.

If bookings and questions interleave instead, both tables go stale after every booking. That is a job for the tree structures from the previous section's warning.

Your turn: the flights already hold base = [2, 0, 5, 1] seats. Apply the bookings [(0, 1, 3), (2, 3, 2)], then answer the queries [0, 3] and [1, 2]. Can you fold base into the difference array so that a single running sum produces the final seat counts? Finally, test your function against a direct simulator.

from itertools import accumulate
# the last lines use build_prefix and range_sum from the warm-up

def range_adds_on(base, ops):
    n = len(base)
    diff = [0] * (n + 1)
    for i, x in enumerate(base):      # each starting value is a one-cell booking
        diff[i] += x
        diff[i + 1] -= x
    for l, r, v in ops:
        diff[l] += v
        diff[r + 1] -= v
    return list(accumulate(diff[:n]))

values = range_adds_on([2, 0, 5, 1], [(0, 1, 3), (2, 3, 2)])
prefix = build_prefix(values)
print(values, range_sum(prefix, 0, 3), range_sum(prefix, 1, 2))   # [5, 3, 7, 3] 18 10

import random
# uses range_adds_on from above and build_prefix / range_sum from the warm-up

def simulate(base, ops, queries):
    arr = base[:]
    for l, r, v in ops:
        for i in range(l, r + 1):
            arr[i] += v
    return arr, [sum(arr[l:r + 1]) for l, r in queries]

for _ in range(2000):
    n = random.randint(1, 7)
    base = [random.randint(-5, 5) for _ in range(n)]
    ops, queries = [], []
    for _ in range(random.randint(0, 5)):
        l = random.randint(0, n - 1)
        ops.append((l, random.randint(l, n - 1), random.randint(-5, 5)))
    for _ in range(3):
        l = random.randint(0, n - 1)
        queries.append((l, random.randint(l, n - 1)))
    values = range_adds_on(base, ops)
    prefix = build_prefix(values)
    got = (values, [range_sum(prefix, l, r) for l, r in queries])
    assert got == simulate(base, ops, queries), (base, ops, queries)
print("all matched")

Final round: no label on the problem

Real problems don't say which move they want. For each one, find the smell, pick the move, and settle the boundaries before you write code.

Challenge 1: Maximum Population Year

LeetCode 1854: Maximum Population Year. Each log [birth, death] describes one person, who counts as alive in every year from birth to death − 1, but not in the year of death. Years run from 1950 to 2050. Return the earliest year with the largest population. [[1950, 1961], [1960, 1971], [1970, 1981]] should give 1960.

1. Which move applies, and what plays the role of the range?
2. Where does the −1 go, and why?
3. How do you make ties go to the earliest year?
4. What would you change if years ran from 0 to 10⁹?

def maximum_population(logs):
    diff = [0] * 101                      # index y - 1950 for years 1950..2050
    for birth, death in logs:
        diff[birth - 1950] += 1
        diff[death - 1950] -= 1           # not alive in the death year
    best_year, best, alive = 1950, 0, 0
    for i in range(101):
        alive += diff[i]
        if alive > best:                  # strict: an equal count later doesn't win
            best, best_year = alive, 1950 + i
    return best_year

print(maximum_population([[1950, 1961], [1960, 1971], [1970, 1981]]))   # 1960

Challenge 2: Find Good Days to Rob the Bank

LeetCode 2100: Find Good Days to Rob the Bank. security[i] is the number of guards on day i. Day i is good if the time days before it are non-increasing into day i and the time days after it are non-decreasing out of it: security[i − time] ≥ … ≥ security[i] ≤ … ≤ security[i + time]. Return every good day. Both n and time go up to 10⁵. security = [5, 3, 3, 3, 5, 6, 2] with time = 2 gives [2, 3].

1. What does checking each day directly cost at these limits?
2. What should each pass remember about day i?
3. What value does an edge day get?

def good_days(security, time):
    n = len(security)
    down = [0] * n                        # empty side: a streak of 0
    for i in range(1, n):
        if security[i - 1] >= security[i]:
            down[i] = down[i - 1] + 1
    up = [0] * n
    for i in range(n - 2, -1, -1):
        if security[i] <= security[i + 1]:
            up[i] = up[i + 1] + 1
    return [i for i in range(n) if down[i] >= time and up[i] >= time]

print(good_days([5, 3, 3, 3, 5, 6, 2], 2))   # [2, 3]

Challenge 3: Sum of Absolute Differences in a Sorted Array

LeetCode 1685: Sum of Absolute Differences in a Sorted Array. nums is sorted in non-decreasing order, with up to 10⁵ elements. Return result where result[i] is the sum of |nums[i] − nums[j]| over all j. [2, 3, 5] gives [4, 3, 5].

1. What does sortedness let you do with the absolute value?
2. After that, which two prefix readings does each side need?

from itertools import accumulate

def abs_diff_sums(nums):
    n = len(nums)
    prefix = list(accumulate(nums, initial=0))
    total = prefix[n]
    result = []
    for i, x in enumerate(nums):
        left = x * i - prefix[i]                              # i values, all <= x
        right = (total - prefix[i + 1]) - x * (n - 1 - i)     # n-1-i values, all >= x
        result.append(left + right)
    return result

print(abs_diff_sums([2, 3, 5]), abs_diff_sums([1, 4, 6, 8, 10]))   # [4, 3, 5] [24, 15, 13, 15, 21]

Cheat sheet: smell → move

Before moving on, pick one problem from this lesson and solve it aloud from a blank editor. Say what each running variable means at a specific moment in the loop, where the empty side gets its identity value, why the boundary write goes at r + 1 (or at to for a half-open range), and which changed constraint would break your solution: a zero under division, a negative number under an early exit, or a query that arrives before the last update. If you can do that, you can take these moves to problems that don't announce them.

Next: Hash Maps & Sets combines prefix sums with a hash map to count subarrays with a target sum. Sliding Window Patterns handles ranges that move instead of ranges that are queried. Trees & Advanced Structures covers the Fenwick and segment trees for updates and queries that interleave.