Segment trees: point updates, range queries

A segment tree answers range queries, such as the smallest value from position l to position r, while single values change, and both the query and the change take O(log n). It stores the answer for each half of the array, each quarter and so on down to single values. Any range is then the combination of at most about 2 log₂ n stored answers, and a change recomputes only the log₂ n answers above it. It works for any associative combine with an identity value: minimum, maximum, sum, gcd, or a custom merge such as the best run of consecutive values. Here it finds the cheapest fare between two days while fares change.

The problem: the cheapest fare between two days

With the fares [450, 380, 520, 380, 610, 300, 700, 340]:

1. cheapest(0, 4) gives (380, 1): days 1 and 3 tie, and day 1 is earlier.
2. After update(1, 500), cheapest(0, 4) gives (380, 3) and cheapest(5, 7) gives (300, 5).
3. After update(5, 900), cheapest(4, 7) gives (340, 7), and cheapest(2, 2) gives (520, 2).

The brute force: scan the range

Read every day of the range and keep the best pair (fare, day). A change is one write, and a question reads up to n fares:

"""The cheapest fare over a range of days, found by scanning the range for every question, with the work counted."""
import random


def run_brute(fares, events):
    fares, answers, reads = list(fares), [], 0
    for kind, x, y in events:
        if kind == "update":
            fares[x] = y
        else:
            best = min((fares[d], d) for d in range(x, y + 1))  # the earliest day wins a tie
            reads += y - x + 1
            answers.append(best)
    return answers, reads


fares = [450, 380, 520, 380, 610, 300, 700, 340]
events = [("cheapest", 0, 4), ("update", 1, 500), ("cheapest", 0, 4), ("cheapest", 5, 7),
          ("update", 5, 900), ("cheapest", 4, 7), ("cheapest", 2, 2)]
print("fares", fares)
print("answers (fare, day):", run_brute(fares, events)[0])

rng = random.Random(8)
last = None
for n in (1_000, 2_000, 4_000):
    fares = [rng.randint(100, 5000) for _ in range(n)]
    events = []
    for _ in range(n):
        if rng.random() < 0.5:
            events.append(("update", rng.randrange(n), rng.randint(100, 5000)))
        else:
            a, b = rng.randrange(n), rng.randrange(n)
            events.append(("cheapest", min(a, b), max(a, b)))
    reads = run_brute(fares, events)[1]
    print(f"n = {n:,} days and {n:,} events: {reads:,} fares read" + (f", x{reads / last:.1f}" if last else ""))
    last = reads
print(f"at 200,000 days and 200,000 events: about {last * (200_000 / 4_000) ** 2:.1e} fares read (estimated)")

fares [450, 380, 520, 380, 610, 300, 700, 340]
answers (fare, day): [(380, 1), (380, 3), (300, 5), (340, 7), (520, 2)]
n = 1,000 days and 1,000 events: 172,828 fares read
n = 2,000 days and 2,000 events: 654,789 fares read, x3.8
n = 4,000 days and 4,000 events: 2,607,959 fares read, x4.0
at 200,000 days and 200,000 events: about 6.5e+09 fares read (estimated)

Doubling the days and the events multiplies the reads by about 4. At the limits that is about 6.5 × 10⁹ fares read, far beyond a time limit of a few seconds in any language.

What to notice

Three faster structures fail here, each for one reason. Prefix sums and Fenwick trees answer a range by subtracting two prefixes, and a minimum cannot be subtracted. A sparse table answers fixed data, and these fares change. What the minimum does have is associativity, with an identity, +∞, which leaves no mark on an answer: the cheapest of a range is the cheaper of the cheapest of its two halves. So store the answer of every half, quarter and single day.

The tree can be written bottom-up, in one array of 2n nodes, or recursively from the root, which is easier to extend. A tree of minimums can also search: it finds the first day from a given day whose fare fits a budget.

The bottom-up tree, step by step Pro: opens with a Pro, Premium or Ultimate pass