Coding Interview Patterns Module 30 – Range queries: Fenwick and segment trees
Choosing a range-query structure
Pick prefix sums, a Fenwick tree, a segment tree or a sparse table from the operations a problem asks for, with every cost counted and timed.
What you will learn
- Pick prefix sums, a Fenwick tree, a segment tree or a sparse table from the operation mix
- Estimate the build, update, query and memory costs of each structure from the input limits
- Distinguish the structures a coding round expects from contest techniques such as Mo's algorithm
- Solve a range-count problem with sorted positions and two binary searches
Before you start
What you’ll learn · Before you start
What you will learn
- Pick prefix sums, a Fenwick tree, a segment tree or a sparse table from the operation mix
- Estimate the build, update, query and memory costs of each structure from the input limits
- Distinguish the structures a coding round expects from contest techniques such as Mo's algorithm
- Solve a range-count problem with sorted positions and two binary searches
Before you start
On this page
A range query asks one question about a stretch of an array: the total of positions 3 to 9, their smallest value, or how often a code appears among them. The structure to build follows from the problem’s operation mix: whether values change while the questions arrive, and how the answers for two parts of a range combine. With no changes and a sum, prefix sums answer each question in O(1). With changes to single values and a sum, a Fenwick tree handles both in O(log n). With no changes and a minimum, maximum or gcd, a sparse table answers in O(1) after O(n log n) work. With changes and any other combine, including changes to whole ranges, a segment tree does each operation in O(log n). This lesson turns those rules into a chart, counts and times all four on the same 100,000 operations in Python and C++, separates what a coding round expects from contest techniques, and solves one problem in full.
Two questions decide the structure
Read two things from the problem before you choose anything.
What changes, and when. The values may never change; the data is then called static. They may change one position at a time, a point update, such as “set position 7 to 40”. Or a whole stretch may change at once, a range update, such as “add 5 to positions 10 to 90”. Ask when the changes arrive, too. If every change comes before the first question, apply them all to a plain array and the data is static from then on.
How the answers for two parts combine. Every structure in this lesson answers a range by combining the answers for smaller pieces of it, so the combine must be associative: combining a with b and then with c gives the same as combining a with the combination of b and c. Sums, products, minimums, maximums, gcd, AND, OR and XOR all are. Two more properties decide the rest:
- The combine can be undone. The total of a range is the total up to its end minus the total before its start. Counts can be undone the same way, and so can XOR, because x XOR x is 0. Prefix sums and Fenwick trees rely on this.
- Overlap does no harm. For a minimum, min(x, x) = x, so two pieces that share some positions still give the right minimum. Maximum, gcd, AND and OR behave the same way; combines like these are called idempotent. A sum is not one: the shared positions would be counted twice. Sparse tables rely on this.
Here are the three properties checked on eight readings:
"""Why the operation decides the structure: a sum can be undone, a minimum cannot, and a minimum may overlap.
Three small checks on the same eight readings, each printed next to the answer worked out the slow way.
"""
readings = [5, 3, 8, 6, 2, 7, 4, 9]
first, last = 2, 5 # the range readings[2] to readings[5]: 8, 6, 2, 7
print("readings:", readings)
print(f"range {first} to {last}:", readings[first:last + 1])
# 1. A total can be undone: the total of the first 6 readings minus the total of the first 2 leaves the range.
prefix_total = [0]
for value in readings:
prefix_total.append(prefix_total[-1] + value)
print()
print("1. Totals: prefix[6] - prefix[2] =", prefix_total[last + 1], "-", prefix_total[first], "=",
prefix_total[last + 1] - prefix_total[first], "| added up directly:", sum(readings[first:last + 1]))
# 2. A minimum cannot be undone. Two lists with the same running minimums can still differ inside a range, so no
# formula over running minimums gives the minimum of a range.
def running_minimums(values):
out, low = [], float("inf")
for value in values:
low = min(low, value)
out.append(low)
return out
a = [1, 9, 5, 9]
b = [1, 9, 7, 9]
print()
print("2. Minimums: running minimums of", a, "are", running_minimums(a))
print(" running minimums of", b, "are", running_minimums(b))
print(" minimum of positions 1 to 2:", min(a[1:3]), "and", min(b[1:3]))
# 3. Two blocks of length 4 cover the range 1 to 6 (length 6) and overlap in positions 3 and 4. For a minimum the
# overlap is harmless, because min(x, x) = x. For a total, the overlap is counted twice.
left_block = readings[1:5] # positions 1 to 4
right_block = readings[3:7] # positions 3 to 6
print()
print("3. Overlapping blocks for positions 1 to 6:", left_block, "and", right_block)
print(" min of the two block minimums:", min(min(left_block), min(right_block)),
"| directly:", min(readings[1:7]))
print(" total of the two block totals:", sum(left_block) + sum(right_block),
"| directly:", sum(readings[1:7]), "(positions 3 and 4 counted twice)")Output
readings: [5, 3, 8, 6, 2, 7, 4, 9]
range 2 to 5: [8, 6, 2, 7]
1. Totals: prefix[6] - prefix[2] = 31 - 8 = 23 | added up directly: 23
2. Minimums: running minimums of [1, 9, 5, 9] are [1, 1, 1, 1]
running minimums of [1, 9, 7, 9] are [1, 1, 1, 1]
minimum of positions 1 to 2: 5 and 7
3. Overlapping blocks for positions 1 to 6: [3, 8, 6, 2] and [6, 2, 7, 4]
min of the two block minimums: 2 | directly: 2
total of the two block totals: 38 | directly: 30 (positions 3 and 4 counted twice)
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 properties.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The first check is the formula of the lesson on prefix sums:
31 − 8 = 23. The second shows that no such formula exists for minimums. The lists [1, 9, 5, 9] and [1, 9, 7, 9]
have the same running minimums, 1 at every position, yet the minimum of positions 1 to 2 is 5 in one and 7 in the
other, so a rule that only sees running minimums cannot give both answers. The third covers positions 1 to 6 with
two blocks of four that share positions 3 and 4: the two block minimums still give the right minimum, 2, while the
two block totals add up to 38 instead of 30.
The four structures at a glance
Each structure is a different trade between the time to build it, to answer a query, to take a change, and its memory:
- Prefix sums keep the running totals with a 0 in front, so a range total is one subtraction. They take O(n) to build and O(1) a query, but a change to one value moves every later running total, which costs O(n). They suit data that stays the same while the questions run.
- A Fenwick tree, also called a binary indexed tree, keeps n partial totals in an array of n + 1 entries, and both an update and a prefix total touch about log₂ n of them. Peter Fenwick published it in 1994 for tables of cumulative frequencies. Entry k holds the total of a block of k & −k values that ends at the k-th value, where k & −k is the lowest set bit of k: 1 for odd k, 4 for k = 12. A range total is two prefix totals subtracted, so it needs a combine that can be undone.
- A segment tree stores the combination of each half, each quarter and so on of the array in the nodes of a binary tree, with the values in its leaves. A query combines O(log n) nodes that cover the range exactly, and a change recomputes the O(log n) nodes above the changed leaf. It works for any associative combine that has an identity element, such as 0 for sums and +∞ for minimums, and with lazy tags, which keep a pending change for a whole node, it also takes changes to whole ranges in O(log n).
- A sparse table stores the combination of every block whose length is a power of two. A query takes the largest power of two that fits in the range and combines just two blocks of that length, one that starts where the range starts and one that ends where it ends. That is O(1), and because the two blocks may overlap, it needs an idempotent combine. Building it takes O(n log n) time and memory, and it has no update: a change means building it again.
Side by side, in two pairs: the structures for data that stays fixed, and those for data that changes.
| Criterion | Prefix sums | Sparse table |
|---|---|---|
| Build | O(n) | O(n log n) |
| Query | O(1) | O(1) |
| Combine | Sum, count, XOR | Min, max, gcd, AND, OR |
| A change | Patch: O(n) | Rebuild: O(n log n) |
| Cells | 100,001 | 1,568,946 |
| Lines | 10 | 13 |
| When to choose | Sums or counts | Min, max or gcd, with many queries |
| Criterion | Fenwick tree | Segment tree |
|---|---|---|
| Build | O(n) | O(n) |
| Query | O(log n) | O(log n) |
| Update | O(log n) | O(log n) |
| Ranges | Add to a range, read one value | Lazy tags: O(log n) |
| Combine | Sum, count, XOR | Any associative |
| Cells | 100,001 | 200,000 |
| Lines | 20 | 27 |
| When to choose | Sums or counts with updates | Other combines, or range updates |
“Lines” counts the code of each structure in structures.py, in the next section, without comments, docstrings
and blank lines, and “Ranges” says what each does when a whole range changes.
For “add to every value from first to last” with questions about single values, a Fenwick tree works on the
differences between neighbours: the change becomes two point updates, at first and at last + 1, and a value is the
total of the differences up to it.
The decision chart
Ask the questions in order; the first “yes” names the structure.
Which range-query structure does the problem need?
Text description of the diagram
The chart has two columns: six questions on the left, asked from top to bottom, and the structure that answers each one on the right.
- Does the query ask about one value inside the range, such as how often a code occurs there? If yes, keep the positions of each value in a sorted list and answer with two binary searches.
- If not: are there no updates, and is the query a sum, a count or an XOR? If yes, use prefix sums, with O(1) a query.
- If not: are there no updates, and is the query a minimum, a maximum, a gcd, an AND or an OR? If yes, use a sparse table, with O(1) a query.
- If not: are there point updates, where one value changes at a time, and is the query a sum, a count or an XOR? If yes, use a Fenwick tree, with O(log n) for each update and query.
- If not: are there point updates or no updates at all, and is the query any other associative combine? If yes, use a segment tree, with O(log n) for each update and query.
- If not: do whole ranges change at once? If yes, use a segment tree with lazy tags, with O(log n) for each update and query.
If none of the six fits, check that the way two parts of a range combine is associative, because every structure in the chart relies on it.
The same rules, grouped by the combine the query needs:
- A sum, a count or an XOR: prefix sums with no changes, a Fenwick tree with point updates, and a segment tree with lazy tags (a lazy segment tree) when whole ranges change. If the queries then read single values, a Fenwick tree on the differences is enough, and two Fenwick trees can also give range totals.
- A minimum, maximum, gcd, AND or OR: a sparse table with no changes, a segment tree with point updates, and a lazy segment tree when whole ranges change.
- Any other associative combine: a segment tree, with or without point updates. A lazy segment tree handles range changes only when a pending change can be applied to a node’s stored answer at once, without visiting the values below it.
The first row of the chart catches a different kind of question: one about a single value inside the range, such as “how many parcels in this stretch are for route 31?”. Those are prefix counts, one count per value, and they get their own structure, built in the worked problem at the end of this lesson.
Estimate before you code
O(log n) says how the cost grows, not how large it is. Counting says how large. The program below runs the code of
structures.py with each structure’s lists swapped for lists that count every read and every write, on 100,000
values and the same 10,000 random ranges and positions for every structure:
Python (structures.py) · structures/structures.py
"""Four range-query structures in their short form, as counts.py and bench.py use them.
Positions count from 0, and every range is inclusive: total(first, last) covers values[first] to values[last].
"""
class PrefixSums:
"""Running totals with a 0 in front. Build O(n), range total O(1), adding to one value O(n)."""
def __init__(self, values):
self.prefix = [0] * (len(values) + 1)
for i, value in enumerate(values):
self.prefix[i + 1] = self.prefix[i] + value
def total(self, first, last):
return self.prefix[last + 1] - self.prefix[first]
def add(self, i, delta):
# Every prefix that contains position i changes: prefix[i + 1] to prefix[n].
for j in range(i + 1, len(self.prefix)):
self.prefix[j] += delta
class FenwickTree:
"""Fenwick (1994). Entry k, counted from 1, holds the total of the k & -k values that end at position k - 1.
Build O(n), adding to one value O(log n), range total O(log n)."""
def __init__(self, values):
self.tree = [0, *values]
for k in range(1, len(self.tree)): # pass each entry's total up to the next entry that covers it
parent = k + (k & -k)
if parent < len(self.tree):
self.tree[parent] += self.tree[k]
def add(self, i, delta):
k = i + 1
while k < len(self.tree):
self.tree[k] += delta
k += k & -k
def prefix_total(self, count):
"""The total of the first `count` values."""
total = 0
while count > 0:
total += self.tree[count]
count -= count & -count
return total
def total(self, first, last):
return self.prefix_total(last + 1) - self.prefix_total(first)
class SegmentTree:
"""Iterative segment tree: node k combines nodes 2k and 2k + 1, and the n values sit in nodes n to 2n - 1.
Any associative combine with an identity works (sum with 0, min with infinity).
Build O(n), setting one value O(log n), range query O(log n)."""
def __init__(self, values, combine, identity):
self.n = n = len(values)
self.combine, self.identity = combine, identity
self.node = [identity] * n + list(values)
for k in range(n - 1, 0, -1):
self.node[k] = combine(self.node[2 * k], self.node[2 * k + 1])
def set(self, i, value):
k = i + self.n
self.node[k] = value
while k > 1:
k //= 2
self.node[k] = self.combine(self.node[2 * k], self.node[2 * k + 1])
def query(self, first, last):
combine, node = self.combine, self.node
left = right = self.identity
lo, hi = first + self.n, last + self.n + 1 # the nodes lo to hi - 1 cover the range
while lo < hi:
if lo & 1:
left = combine(left, node[lo])
lo += 1
if hi & 1:
hi -= 1
right = combine(node[hi], right)
lo //= 2
hi //= 2
return combine(left, right)
class SparseTable:
"""levels[k][i] combines values[i] to values[i + 2**k - 1]. Build O(n log n). A query combines two blocks that
may overlap, so it is O(1), and right only for operations where overlap does no harm (min, max, gcd).
It has no update: a changed value means building it again."""
def __init__(self, values, combine):
self.combine = combine
self.levels = [list(values)]
width = 1
while 2 * width <= len(values):
below = self.levels[-1]
self.levels.append([combine(below[i], below[i + width]) for i in range(len(below) - width)])
width *= 2
def query(self, first, last):
k = (last - first + 1).bit_length() - 1 # the largest power of two that fits in the range
row = self.levels[k]
return self.combine(row[first], row[last - (1 << k) + 1])Python (counts.py) · structures/counts.py
"""How many cells of each structure one operation reads and writes, counted on 100,000 values.
Each structure from structures.py gets its lists swapped for lists that count every read and every write, so the
counts come from the same code that bench.py times. Every structure gets the same 10,000 random ranges and positions.
"""
import random
from structures import FenwickTree, PrefixSums, SegmentTree, SparseTable
class CountingList(list):
"""A list that counts the items read from it and written to it."""
reads = 0
writes = 0
def __getitem__(self, index):
CountingList.reads += 1
return super().__getitem__(index)
def __setitem__(self, index, value):
CountingList.writes += 1
super().__setitem__(index, value)
def counted(operations, run):
"""Average reads and writes per call of run(operation), and the largest reads + writes of one call."""
reads = writes = largest = 0
for operation in operations:
CountingList.reads = CountingList.writes = 0
run(*operation)
reads += CountingList.reads
writes += CountingList.writes
largest = max(largest, CountingList.reads + CountingList.writes)
return reads / len(operations), writes / len(operations), largest
n, trials = 100_000, 10_000
rng = random.Random(30)
values = [rng.randint(1, 10**9) for _ in range(n)]
ranges = [tuple(sorted((rng.randrange(n), rng.randrange(n)))) for _ in range(trials)]
changes = [(rng.randrange(n), rng.randint(1, 1000)) for _ in range(trials)]
prefix = PrefixSums(values)
prefix.prefix = CountingList(prefix.prefix)
fenwick = FenwickTree(values)
fenwick.tree = CountingList(fenwick.tree)
sums = SegmentTree(values, lambda x, y: x + y, 0)
sums.node = CountingList(sums.node)
mins = SegmentTree(values, min, float("inf"))
mins.node = CountingList(mins.node)
table = SparseTable(values, min)
table.levels = [CountingList(row) for row in table.levels]
rows = [
("range total", "prefix sums", ranges, prefix.total),
("range total", "Fenwick tree", ranges, fenwick.total),
("range total", "segment tree", ranges, sums.query),
("range minimum", "segment tree", ranges, mins.query),
("range minimum", "sparse table", ranges, table.query),
("add to one value", "Fenwick tree", changes, fenwick.add),
("set one value", "segment tree", changes, mins.set),
]
print(f"{n:,} values, the same {trials:,} random ranges and positions for every structure")
print("cells read and written per operation, on average, and the most in one operation\n")
print(f"{'operation':<17}{'structure':<14}{'reads':>7}{'writes':>8}{'most':>6}")
for operation, structure, inputs, run in rows:
reads, writes, largest = counted(inputs, run)
print(f"{operation:<17}{structure:<14}{reads:>7.1f}{writes:>8.1f}{largest:>6}")
print(f"\nThe average range covers {sum(last - first + 1 for first, last in ranges) / trials:,.0f} values.")
print(f"The sparse table holds {sum(len(row) for row in table.levels):,} cells in {len(table.levels)} rows.")Output
100,000 values, the same 10,000 random ranges and positions for every structure cells read and written per operation, on average, and the most in one operation operation structure reads writes most range total prefix sums 2.0 0.0 2 range total Fenwick tree 16.3 0.0 26 range total segment tree 14.4 0.0 25 range minimum segment tree 14.4 0.0 25 range minimum sparse table 2.0 0.0 2 add to one value Fenwick tree 8.8 8.8 32 set one value segment tree 33.4 17.7 52 The average range covers 33,399 values. The sparse table holds 1,568,946 cells in 17 rows.
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 counts.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
- A range total read 2 cells with prefix sums, 16.3 on average with the Fenwick tree and 14.4 with the segment tree. The bottom-up segment tree reads only the nodes it combines, so on reads alone it is close to the Fenwick tree. It does more work for each node it visits, which the timings below show.
- A sparse table read 2 cells for any range, the two blocks.
- A change wrote 8.8 Fenwick entries on average. Setting one value of the segment tree wrote 17.7 nodes and read 33.4, the two children of every node on the way to the root.
- The slow options cost thousands of times more. A brute force reads every value of the range, 33,399 on average for these ranges, because a random range covers about a third of the array. Patching prefix sums after a change rewrites every later total, 50,000 on average, and building the sparse table again writes all 1,568,946 cells.
So 100,000 operations on a Fenwick tree or a segment tree make a few million reads and writes, while a brute force reads about 3.3 × 10⁹ values for 100,000 range totals. The same counts give the memory. With 64-bit numbers, the sparse table’s 1,568,946 cells take about 12.6 MB, against 1.6 MB for the segment tree’s 200,000 nodes and 0.8 MB for the Fenwick tree. At n = 10⁶ the sparse table has 20 rows and about 19 million cells, about 152 MB with 64-bit numbers, so count before you pick it for a large n.
Logarithm & Antilog Calculator Work out log₂ n for your own limits: the levels a Fenwick tree or a segment tree walks, and one less than the number of rows of a sparse table.Measured: four mixes in two languages
Counts leave out what each step costs. Here are the same structures timed, with a brute force, on four mixes of 100,000 operations over 100,000 values. Every time includes building the structure. The values and the operations come from a small seeded generator, so the C++ program after it answers exactly the same questions and has to print the same checksums:
"""Times a brute force and the four structures of structures.py on four mixes of 100,000 operations.
Each time is processor time for the whole mix, building the structure included, and the fastest of 3 rounds. A mix
whose every operation costs O(n) would take minutes here, so it is timed on its first operations and scaled up, and
the sparse table's rebuilds are estimated from one build (both marked *). The values and operations come from a small
seeded generator, SplitMix64, written the same way in bench.cpp: both programs answer the same questions, so they
print the same checksums.
"""
import operator
import platform
import time
from structures import FenwickTree, PrefixSums, SegmentTree, SparseTable
MASK = (1 << 64) - 1
N = OPERATIONS = 100_000
ROUNDS = 3
class SplitMix64:
"""A seeded generator of 64-bit numbers."""
def __init__(self, seed):
self.state = seed
def below(self, bound):
self.state = (self.state + 0x9E3779B97F4A7C15) & MASK
z = self.state
z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & MASK
z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & MASK
return (z ^ (z >> 31)) % bound
gen = SplitMix64(30)
values = [gen.below(10**9) + 1 for _ in range(N)]
def mix(updates, new_number=None):
"""(0, first, last) asks about a range; (1, i, number) changes position i, about half the time if updates."""
out = []
for _ in range(OPERATIONS):
if updates and gen.below(2):
out.append((1, gen.below(N), new_number()))
else:
a, b = gen.below(N), gen.below(N)
out.append((0, min(a, b), max(a, b)))
return out
MIXES = {
"A": mix(False),
"B": mix(True, lambda: gen.below(1000) + 1), # add 1 to 1,000 to one value
"C": mix(False),
"D": mix(True, lambda: gen.below(10**9) + 1), # set one value
}
# Each run builds its structure, does every operation it is given and returns the total of its answers (mod 2**64).
def brute_totals(ops):
a, total = list(values), 0
for kind, x, y in ops:
if kind:
a[x] += y
else:
total += sum(a[x:y + 1])
return total & MASK
def prefix_totals(ops):
p, total = PrefixSums(values), 0
for kind, x, y in ops:
if kind:
p.add(x, y)
else:
total += p.total(x, y)
return total & MASK
def fenwick_totals(ops):
f, total = FenwickTree(values), 0
for kind, x, y in ops:
if kind:
f.add(x, y)
else:
total += f.total(x, y)
return total & MASK
def segment_totals(ops):
t, total = SegmentTree(values, operator.add, 0), 0
for kind, x, y in ops:
if kind:
t.set(x, t.node[t.n + x] + y)
else:
total += t.query(x, y)
return total & MASK
def brute_minimums(ops):
a, total = list(values), 0
for kind, x, y in ops:
if kind:
a[x] = y
else:
total += min(a[x:y + 1])
return total & MASK
def segment_minimums(ops):
t, total = SegmentTree(values, min, float("inf")), 0
for kind, x, y in ops:
if kind:
t.set(x, y)
else:
total += t.query(x, y)
return total & MASK
def sparse_minimums(queries):
table, total = SparseTable(values, min), 0
for _, first, last in queries:
total += table.query(first, last)
return total & MASK
def timed(run, ops):
"""The fastest of ROUNDS runs, in milliseconds of processor time, and the run's checksum."""
best = float("inf")
for _ in range(ROUNDS):
start = time.process_time()
checksum = run(ops)
best = min(best, time.process_time() - start)
return best * 1000, checksum
def scaled(run, ops, sample, check):
"""Milliseconds for the first `sample` operations, scaled to the whole mix; the answers must equal check's."""
ms, checksum = timed(run, ops[:sample])
assert checksum == check(ops[:sample]), f"{run.__name__} gives other answers than {check.__name__}"
return ms * len(ops) / sample
def rebuilt_after_each_change(ops):
"""A sparse table has no update, so every change builds it again: one build, timed, times the number of changes,
plus the queries on a table built once."""
changes = sum(kind for kind, _, _ in ops)
build_ms, _ = timed(lambda _: SparseTable(values, min), None)
query_ms, _ = timed(sparse_minimums, [op for op in ops if not op[0]])
return build_ms * changes + query_ms
checksums = {}
def whole(run, key):
ms, checksum = timed(run, MIXES[key])
assert checksums.setdefault(key, checksum) == checksum, f"{run.__name__} gives other answers on mix {key}"
return f"{ms:,.0f}"
A, B, C, D = MIXES["A"], MIXES["B"], MIXES["C"], MIXES["D"]
rows = [
("brute force", [f"{scaled(brute_totals, A, 1000, fenwick_totals):,.0f}*", f"{scaled(brute_totals, B, 1000, fenwick_totals):,.0f}*",
f"{scaled(brute_minimums, C, 1000, segment_minimums):,.0f}*", f"{scaled(brute_minimums, D, 1000, segment_minimums):,.0f}*"]),
("prefix sums", [whole(prefix_totals, "A"), f"{scaled(prefix_totals, B, 100, fenwick_totals):,.0f}*", "-", "-"]),
("Fenwick tree", [whole(fenwick_totals, "A"), whole(fenwick_totals, "B"), "-", "-"]),
("segment tree", [whole(segment_totals, "A"), whole(segment_totals, "B"), whole(segment_minimums, "C"), whole(segment_minimums, "D")]),
("sparse table", ["-", "-", whole(sparse_minimums, "C"), f"{rebuilt_after_each_change(D):,.0f}*"]),
]
print(f"Mixes of {OPERATIONS:,} operations on {N:,} values, {platform.python_implementation()} {platform.python_version()}:")
print(" A range totals only")
print(" B range totals and additions to one value, about half each")
print(" C range minimums only")
print(" D range minimums and changes to one value, about half each")
print(f"Milliseconds of processor time for the whole mix, building included, the fastest of {ROUNDS} rounds.")
print("* = estimated: timed on the first operations and scaled up, or, for the sparse table in D, one build")
print(" timed and counted once per change. - = the structure cannot answer that mix.\n")
print(f"{'':<14}" + "".join(f"{key:>13}" for key in MIXES))
for name, cells in rows:
print(f"{name:<14}" + "".join(f"{cell:>13}" for cell in cells))
print("\nEvery structure gave the same answers. Checksums of the answers, A to D:")
print(" " + " ".join(f"{checksums[key]:016x}" for key in MIXES))Output
Mixes of 100,000 operations on 100,000 values, CPython 3.14.8:
A range totals only
B range totals and additions to one value, about half each
C range minimums only
D range minimums and changes to one value, about half each
Milliseconds of processor time for the whole mix, building included, the fastest of 3 rounds.
* = estimated: timed on the first operations and scaled up, or, for the sparse table in D, one build
timed and counted once per change. - = the structure cannot answer that mix.
A B C D
brute force 17,149* 8,642* 34,152* 14,017*
prefix sums 14 69,033* - -
Fenwick tree 118 105 - -
segment tree 178 179 159 205
sparse table - - 87 3,063,267*
Every structure gave the same answers. Checksums of the answers, A to D:
17249e1ec2bae3ac 0b9f6f82631b48f8 000000045bfd3373 000000029ebdeb7c
This output changes from run to run: the times depend on the computer and on what else it is doing; the checksums are the same on every run
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 bench.py
C++ · compiled/bench.cpp
// The benchmark of bench.py in C++: the same four structures, the same SplitMix64 generator and the same four mixes
// of 100,000 operations on 100,000 values, so the checksums must equal the Python ones. Times are processor time
// (std::clock) for the whole mix, building included, the fastest of 3 rounds. Here even the brute force runs every
// operation; only the sparse table's rebuilds in mix D are estimated, from one build per change (marked *).
#include <algorithm>
#include <bit>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <limits>
#include <string>
#include <vector>
using i64 = std::int64_t;
using u64 = std::uint64_t;
constexpr int N = 100'000, OPERATIONS = 100'000, ROUNDS = 3;
struct SplitMix64 {
u64 state;
u64 below(u64 bound) {
state += 0x9E3779B97F4A7C15ULL;
u64 z = state;
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
return (z ^ (z >> 31)) % bound;
}
};
struct PrefixSums { // build O(n), range total O(1), adding to one value O(n)
std::vector<i64> prefix;
explicit PrefixSums(const std::vector<i64>& v) : prefix(v.size() + 1, 0) {
for (std::size_t i = 0; i < v.size(); ++i) prefix[i + 1] = prefix[i] + v[i];
}
i64 total(int first, int last) const { return prefix[last + 1] - prefix[first]; }
void add(int i, i64 delta) {
for (std::size_t j = i + 1; j < prefix.size(); ++j) prefix[j] += delta;
}
};
struct FenwickTree { // entry k (from 1) holds the total of the k & -k values ending at position k - 1
std::vector<i64> tree;
explicit FenwickTree(const std::vector<i64>& v) : tree(v.size() + 1, 0) {
std::copy(v.begin(), v.end(), tree.begin() + 1);
for (std::size_t k = 1; k < tree.size(); ++k) {
std::size_t parent = k + (k & -k);
if (parent < tree.size()) tree[parent] += tree[k];
}
}
void add(int i, i64 delta) {
for (std::size_t k = i + 1; k < tree.size(); k += k & -k) tree[k] += delta;
}
i64 prefix_total(std::size_t count) const {
i64 total = 0;
for (; count > 0; count -= count & -count) total += tree[count];
return total;
}
i64 total(int first, int last) const { return prefix_total(last + 1) - prefix_total(first); }
};
template <class Combine>
struct SegmentTree { // node k combines nodes 2k and 2k + 1; the values sit in nodes n to 2n - 1
int n;
std::vector<i64> node;
Combine combine;
i64 identity;
SegmentTree(const std::vector<i64>& v, Combine c, i64 id) : n(int(v.size())), node(2 * v.size(), id), combine(c), identity(id) {
std::copy(v.begin(), v.end(), node.begin() + n);
for (int k = n - 1; k > 0; --k) node[k] = combine(node[2 * k], node[2 * k + 1]);
}
void set(int i, i64 value) {
int k = i + n;
node[k] = value;
for (k /= 2; k >= 1; k /= 2) node[k] = combine(node[2 * k], node[2 * k + 1]);
}
i64 query(int first, int last) const {
i64 left = identity, right = identity;
for (int lo = first + n, hi = last + n + 1; lo < hi; lo /= 2, hi /= 2) {
if (lo & 1) left = combine(left, node[lo++]);
if (hi & 1) right = combine(node[--hi], right);
}
return combine(left, right);
}
};
struct SparseTable { // levels[k][i] = min of v[i .. i + 2^k - 1]; O(1) queries, no update
std::vector<std::vector<i64>> levels;
explicit SparseTable(const std::vector<i64>& v) : levels{v} {
for (std::size_t width = 1; 2 * width <= v.size(); width *= 2) {
const std::vector<i64>& below = levels.back();
std::vector<i64> row(below.size() - width);
for (std::size_t i = 0; i < row.size(); ++i) row[i] = std::min(below[i], below[i + width]);
levels.push_back(std::move(row));
}
}
i64 query(int first, int last) const {
int k = std::bit_width(unsigned(last - first + 1)) - 1;
return std::min(levels[k][first], levels[k][last - (1 << k) + 1]);
}
};
struct Op {
int kind, x;
i64 y; // kind 0: a range x to y; kind 1: position x and a number y
};
std::vector<Op> mix(SplitMix64& gen, bool updates, const std::function<i64()>& new_number) {
std::vector<Op> out;
for (int i = 0; i < OPERATIONS; ++i) {
if (updates && gen.below(2)) {
int x = int(gen.below(N));
out.push_back({1, x, new_number()});
} else {
i64 a = i64(gen.below(N)), b = i64(gen.below(N));
out.push_back({0, int(std::min(a, b)), std::max(a, b)});
}
}
return out;
}
std::vector<i64> values;
u64 brute_totals(const std::vector<Op>& ops) {
std::vector<i64> a = values;
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) a[op.x] += op.y;
else {
i64 s = 0;
for (i64 i = op.x; i <= op.y; ++i) s += a[i];
total += u64(s);
}
}
return total;
}
u64 prefix_totals(const std::vector<Op>& ops) {
PrefixSums p(values);
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) p.add(op.x, op.y);
else total += u64(p.total(op.x, int(op.y)));
}
return total;
}
u64 fenwick_totals(const std::vector<Op>& ops) {
FenwickTree f(values);
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) f.add(op.x, op.y);
else total += u64(f.total(op.x, int(op.y)));
}
return total;
}
u64 segment_totals(const std::vector<Op>& ops) {
SegmentTree t(values, std::plus<i64>{}, 0);
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) t.set(op.x, t.node[t.n + op.x] + op.y);
else total += u64(t.query(op.x, int(op.y)));
}
return total;
}
u64 brute_minimums(const std::vector<Op>& ops) {
std::vector<i64> a = values;
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) a[op.x] = op.y;
else {
i64 m = a[op.x];
for (i64 i = op.x + 1; i <= op.y; ++i) m = std::min(m, a[i]);
total += u64(m);
}
}
return total;
}
u64 segment_minimums(const std::vector<Op>& ops) {
auto smaller = [](i64 p, i64 q) { return std::min(p, q); };
SegmentTree t(values, smaller, std::numeric_limits<i64>::max());
u64 total = 0;
for (const Op& op : ops) {
if (op.kind) t.set(op.x, op.y);
else total += u64(t.query(op.x, int(op.y)));
}
return total;
}
u64 sparse_minimums(const std::vector<Op>& queries) {
SparseTable table(values);
u64 total = 0;
for (const Op& op : queries) total += u64(table.query(op.x, int(op.y)));
return total;
}
// The fastest of ROUNDS runs, in milliseconds of processor time; the checksum goes to *checksum.
double timed(u64 (*run)(const std::vector<Op>&), const std::vector<Op>& ops, u64* checksum) {
double best = 1e300;
for (int r = 0; r < ROUNDS; ++r) {
std::clock_t start = std::clock();
*checksum = run(ops);
best = std::min(best, double(std::clock() - start) * 1000.0 / CLOCKS_PER_SEC);
}
return best;
}
u64 checksums[4];
bool seen[4];
std::string whole(u64 (*run)(const std::vector<Op>&), const std::vector<Op>& ops, int key) {
u64 checksum;
double ms = timed(run, ops, &checksum);
if (seen[key] && checksums[key] != checksum) {
std::printf("mix %c: the answers differ\n", 'A' + key);
std::exit(1);
}
seen[key] = true;
checksums[key] = checksum;
char cell[32];
std::snprintf(cell, sizeof cell, "%.1f", ms);
return cell;
}
std::string rebuilt_after_each_change(const std::vector<Op>& ops) {
int changes = 0;
std::vector<Op> queries;
for (const Op& op : ops) {
if (op.kind) ++changes;
else queries.push_back(op);
}
double build_ms = 1e300;
for (int r = 0; r < ROUNDS; ++r) {
std::clock_t start = std::clock();
SparseTable table(values);
build_ms = std::min(build_ms, double(std::clock() - start) * 1000.0 / CLOCKS_PER_SEC);
if (table.levels.empty()) return "?";
}
u64 checksum;
double query_ms = timed(sparse_minimums, queries, &checksum);
std::string digits = std::to_string((long long)(build_ms * changes + query_ms + 0.5)), cell;
for (std::size_t i = 0; i < digits.size(); ++i) { // 29537 -> 29,537
if (i > 0 && (digits.size() - i) % 3 == 0) cell += ',';
cell += digits[i];
}
return cell + "*";
}
int main() {
SplitMix64 gen{30};
for (int i = 0; i < N; ++i) values.push_back(i64(gen.below(1'000'000'000)) + 1);
std::vector<Op> A = mix(gen, false, nullptr);
std::vector<Op> B = mix(gen, true, [&] { return i64(gen.below(1000)) + 1; });
std::vector<Op> C = mix(gen, false, nullptr);
std::vector<Op> D = mix(gen, true, [&] { return i64(gen.below(1'000'000'000)) + 1; });
struct Row {
const char* name;
std::string cells[4];
};
std::vector<Row> rows;
rows.push_back({"brute force", {whole(brute_totals, A, 0), whole(brute_totals, B, 1), whole(brute_minimums, C, 2), whole(brute_minimums, D, 3)}});
rows.push_back({"prefix sums", {whole(prefix_totals, A, 0), whole(prefix_totals, B, 1), "-", "-"}});
rows.push_back({"Fenwick tree", {whole(fenwick_totals, A, 0), whole(fenwick_totals, B, 1), "-", "-"}});
rows.push_back({"segment tree", {whole(segment_totals, A, 0), whole(segment_totals, B, 1), whole(segment_minimums, C, 2), whole(segment_minimums, D, 3)}});
rows.push_back({"sparse table", {"-", "-", whole(sparse_minimums, C, 2), rebuilt_after_each_change(D)}});
std::printf("Mixes of 100,000 operations on 100,000 values, the same as bench.py, in C++ (-O2):\n");
std::printf("Milliseconds of processor time for the whole mix, building included, the fastest of %d rounds.\n", ROUNDS);
std::printf("* = estimated: one build timed and counted once per change. - = the structure cannot answer that mix.\n\n");
std::printf("%-14s%13s%13s%13s%13s\n", "", "A", "B", "C", "D");
for (const Row& row : rows) {
std::printf("%-14s", row.name);
for (const std::string& cell : row.cells) std::printf("%13s", cell.c_str());
std::printf("\n");
}
std::printf("\nEvery structure gave the same answers. Checksums of the answers, A to D:\n ");
for (u64 checksum : checksums) std::printf(" %016llx", (unsigned long long)checksum);
std::printf("\n");
}Build and run · compiled/bench_session.py
from session import run, versions
# bench.cpp built with optimisation, as judges build C++: the same mixes as bench.py, so the same checksums.
versions("clang++ --version")
run("""
clang++ -std=c++23 -O2 -Wall -Wextra bench.cpp -o bench && ./bench
""")Output
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -O2 -Wall -Wextra bench.cpp -o bench && ./bench
Mixes of 100,000 operations on 100,000 values, the same as bench.py, in C++ (-O2):
Milliseconds of processor time for the whole mix, building included, the fastest of 3 rounds.
* = estimated: one build timed and counted once per change. - = the structure cannot answer that mix.
A B C D
brute force 222.3 117.6 448.8 262.5
prefix sums 0.2 581.4 - -
Fenwick tree 2.9 3.0 - -
segment tree 12.4 8.2 11.3 7.7
sparse table - - 0.9 26,688*
Every structure gave the same answers. Checksums of the answers, A to D:
17249e1ec2bae3ac 0b9f6f82631b48f8 000000045bfd3373 000000029ebdeb7c
This output changes from run to run: the times depend on the computer and on what else it is doing; the checksums are the same on every run
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 bench_session.py
A run on another computer, or a second run on this one, gives other numbers; the comparisons below are the part to
check against your own. Both programs measure the processor time of their own process, with time.process_time()
in Python and std::clock in C++, which other programs on the computer disturb less than the time on a clock.
- The structure mattered more than the language. Every structure answered its mixes in well under a second in CPython, while the brute force, estimated from its first 1,000 operations, came out at least 40 times slower than the best structure for each mix. C++ ran the brute force for real, in hundreds of milliseconds a mix, against about a dozen milliseconds or less for the structures.
- On sums, the Fenwick tree beat the segment tree in both languages. Its loops are simpler: one addition and one bit operation for each step, with no branches to choose a side.
- On minimums of fixed data, the sparse table beat the segment tree in both languages, its O(n log n) build included.
- Updates change the ranking. Prefix sums, the fastest for fixed data, needed an estimated minute or more in CPython for mix B, because each change rewrites tens of thousands of totals. A sparse table built again after each change would need about an hour in CPython and tens of seconds in C++, both estimated.
Coding rounds and contests
For a coding round, be able to write prefix sums, a Fenwick tree and a segment tree with point updates from memory, and to explain lazy tags and sparse tables. Together they answer every row of the chart, at the 10⁵ to 2 × 10⁵ operations that O(log n) handles comfortably. Several other techniques belong to programming contests, and are worth knowing by name:
- Square-root decomposition splits the array into blocks of about √n values and stores an answer for each block, so a change costs O(1) and a range total O(√n): about 316 blocks of 316 values at n = 100,000.
- Mo’s algorithm answers questions that are all known in advance. It sorts them so that a window, which adds or removes one value at a time, moves O(n√n) steps in all for n questions over n values, which suits questions such as “how many different values lie in this range?”.
- Persistent segment trees keep every earlier version of the tree, because an update copies only the O(log n) nodes it changes.
- Segment trees whose nodes hold a structure, such as a sorted list or a count of every value in the node’s range, answer questions such as “how many values in this range are below x?” at O(log n) node visits, each costing the time of its structure.
Each needs more code and more care than the four structures above. They pay off when every question is known in advance, when the question is about different values or earlier versions, or when a log factor is too much at the limits. In a coding round, reaching for one of them usually means that a simpler row of the chart was missed, so read the operation mix again first.
In a live round
Name the structure from the operation mix, and say why the simpler ones fail: “Values change one at a time and every question is a range total, so a Fenwick tree gives O(log n) for both, about 17 steps at 10⁵. Prefix sums would cost O(n) for every change. A segment tree would also work, with more code.”
A problem solved in full: route counts on a parcel log
Here is the first row of the chart on a complete problem, taken through every step a coding round expects: a slow correct answer, the observation that leads to a fast one, the fast one with its proof, a trace, its cost, code in five languages, a stress test against the slow answer, edge cases and follow-ups.
The problem
A parcel sorting centre scans parcels one after another as they pass on a belt, and routes[i] is the route code
of the parcel scanned i-th. The shift report asks many questions of one kind: how many of the parcels scanned from
position first to position last, both included, are for route code? Write route_counts(routes, queries)
to answer each query (first, last, code), giving the answers as a list in the order of the queries. The log has
between 1 and 200,000 scans, the report asks between 1 and 200,000 questions, route codes are whole numbers from 1
to 10⁹, a query may name a code that no parcel has, and every query has 0 ≤ first ≤ last ≤ n − 1.
For routes = [31, 58, 31, 31, 72, 58, 31] and the queries (0, 6, 31), (1, 5, 58), (2, 3, 31), (4, 4, 58) and
(0, 6, 99), the answers are 4, 2, 2, 0 and 0. Scan 4 holds a parcel for route 72, not 58, and no parcel at all is
for route 99.
Brute force first
Walk through the stretch of each query and count the matches:
def route_counts_slow(routes, queries):
"""For each query (first, last, code): count the parcels from first to last whose route is code, one by one."""
return [sum(1 for i in range(first, last + 1) if routes[i] == code) for first, last, code in queries]
if __name__ == "__main__":
routes = [31, 58, 31, 31, 72, 58, 31]
queries = [(0, 6, 31), (1, 5, 58), (2, 3, 31), (4, 4, 58), (0, 6, 99)]
print(route_counts_slow(routes, queries))Output
[4, 2, 2, 0, 0]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
It cannot be wrong, since it looks at every scan, but each query reads up to n codes, so q queries cost O(n × q): up to 200,000 × 200,000 = 4 × 10¹⁰ comparisons at the limits. The lesson on reading constraints budgets roughly 10⁸ simple steps each second in a compiled language and 10⁷ in CPython, which puts this at several minutes in C++ and more than an hour in Python, far beyond any time limit. It still earns its place: the stress test below uses it to check the fast version.
What to notice
The log never changes, and the answer is a count, which can be undone: the count from first to last is the count
up to last minus the count before first. The chart’s second row would say prefix sums, but prefix counts need one
array per route code, count[c][i] = how many of the first i parcels are for route c. With up to 200,000 different
codes, that is up to 200,000 arrays of 200,001 entries, about 4 × 10¹⁰ numbers, and the memory estimate rules it out
before any code is written.
Look at what one of those arrays holds. count[c] grows by one at each position of route c and stays flat
everywhere else, so the positions of c carry all of its information. Keep only those, in a sorted list. The number
of positions at or before last is the prefix count up to last, and a binary search finds it in O(log n). The lists
hold n positions in all, one for each parcel, and that is the first row of the chart.
The fast version, step by step
- Make an empty dictionary,
positions. - In one pass over the log, append each scan position
ito the list of its route code. Positions arrive in increasing order, so every list is sorted without sorting it. - For a query
(first, last, code), take the list ofcode, or an empty list if no parcel has that code, and returnbisect_right(list, last) - bisect_left(list, first): the positions at or beforelast, minus the positions beforefirst.
The Python and JavaScript versions run on this page; the Java, C++ and Go versions follow, built and run in one session:
Python · routes/routes.py
from bisect import bisect_left, bisect_right
def route_counts(routes, queries):
"""For each query (first, last, code): how many parcels from first to last are for route code."""
positions = {}
for i, code in enumerate(routes):
positions.setdefault(code, []).append(i) # i only grows, so every list is sorted
answers = []
for first, last, code in queries:
seen = positions.get(code, [])
answers.append(bisect_right(seen, last) - bisect_left(seen, first))
return answers
if __name__ == "__main__":
routes = [31, 58, 31, 31, 72, 58, 31]
queries = [(0, 6, 31), (1, 5, 58), (2, 3, 31), (4, 4, 58), (0, 6, 99)]
print(route_counts(routes, queries))Output
[4, 2, 2, 0, 0]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 routes.py
JavaScript · routes/routes.mjs
// The first index of a sorted array whose value is >= target (the array's length if there is none).
function lowerBound(sorted, target) {
let lo = 0;
let hi = sorted.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// For each query [first, last, code]: how many parcels from first to last are for route code.
export function routeCounts(routes, queries) {
const positions = new Map();
routes.forEach((code, i) => {
if (!positions.has(code)) positions.set(code, []);
positions.get(code).push(i); // i only grows, so every array is sorted
});
return queries.map(([first, last, code]) => {
const seen = positions.get(code) ?? [];
return lowerBound(seen, last + 1) - lowerBound(seen, first);
});
}
const routes = [31, 58, 31, 31, 72, 58, 31];
const queries = [[0, 6, 31], [1, 5, 58], [2, 3, 31], [4, 4, 58], [0, 6, 99]];
console.log(JSON.stringify(routeCounts(routes, queries)));Output
[4,2,2,0,0]
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node routes.mjs
Runs on this device, in your browser. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
Java · compiled/Routes.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Routes {
/** The first index of a sorted list whose value is >= target (the list's size if there is none). */
static int lowerBound(List<Integer> sorted, int target) {
int lo = 0, hi = sorted.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (sorted.get(mid) < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
/** For each query {first, last, code}: how many parcels from first to last are for route code. */
static int[] routeCounts(int[] routes, int[][] queries) {
Map<Integer, List<Integer>> positions = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
positions.computeIfAbsent(routes[i], code -> new ArrayList<>()).add(i); // i only grows: sorted
}
int[] answers = new int[queries.length];
for (int j = 0; j < queries.length; j++) {
int first = queries[j][0], last = queries[j][1], code = queries[j][2];
List<Integer> seen = positions.getOrDefault(code, List.of());
answers[j] = lowerBound(seen, last + 1) - lowerBound(seen, first);
}
return answers;
}
public static void main(String[] args) {
int[] routes = {31, 58, 31, 31, 72, 58, 31};
int[][] queries = {{0, 6, 31}, {1, 5, 58}, {2, 3, 31}, {4, 4, 58}, {0, 6, 99}};
System.out.println(Arrays.toString(routeCounts(routes, queries)));
}
}C++ · compiled/routes.cpp
#include <algorithm>
#include <array>
#include <cstdio>
#include <unordered_map>
#include <vector>
// For each query {first, last, code}: how many parcels from first to last are for route code.
std::vector<int> route_counts(const std::vector<int>& routes, const std::vector<std::array<int, 3>>& queries) {
std::unordered_map<int, std::vector<int>> positions;
for (int i = 0; i < int(routes.size()); ++i) positions[routes[i]].push_back(i); // i only grows: sorted
std::vector<int> answers;
answers.reserve(queries.size());
for (const auto& [first, last, code] : queries) {
auto found = positions.find(code); // positions[code] would insert an empty list for an unknown code
if (found == positions.end()) {
answers.push_back(0);
continue;
}
const std::vector<int>& seen = found->second;
auto up_to_last = std::upper_bound(seen.begin(), seen.end(), last);
auto from_first = std::lower_bound(seen.begin(), seen.end(), first);
answers.push_back(int(up_to_last - from_first));
}
return answers;
}
int main() {
std::vector<int> routes = {31, 58, 31, 31, 72, 58, 31};
std::vector<std::array<int, 3>> queries = {{0, 6, 31}, {1, 5, 58}, {2, 3, 31}, {4, 4, 58}, {0, 6, 99}};
std::vector<int> answers = route_counts(routes, queries);
for (std::size_t j = 0; j < answers.size(); ++j) std::printf(j ? " %d" : "%d", answers[j]);
std::printf("\n");
}Go · compiled/routes.go
package main
import (
"fmt"
"sort"
)
// routeCounts answers each query {first, last, code}: how many parcels from first to last are for route code.
func routeCounts(routes []int, queries [][3]int) []int {
positions := map[int][]int{}
for i, code := range routes {
positions[code] = append(positions[code], i) // i only grows, so every slice is sorted
}
answers := make([]int, len(queries))
for j, q := range queries {
first, last, code := q[0], q[1], q[2]
seen := positions[code] // a code with no parcel gives a nil slice, and adds no key
answers[j] = sort.SearchInts(seen, last+1) - sort.SearchInts(seen, first)
}
return answers
}
func main() {
routes := []int{31, 58, 31, 31, 72, 58, 31}
queries := [][3]int{{0, 6, 31}, {1, 5, 58}, {2, 3, 31}, {4, 4, 58}, {0, 6, 99}}
fmt.Println(routeCounts(routes, queries))
}Build and run all three · compiled/routes_session.py
from session import run, versions
# The five example queries in Java, C++ and Go: Routes.java run as a single source file, routes.cpp with the
# address and undefined-behaviour sanitizers on.
versions("java -version", "clang++ --version", "go version")
run("""
java Routes.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined routes.cpp -o routes && ./routes
go run routes.go
""")Output
# openjdk version "25.0.4.1" LTS # Apple clang version 21.0.0 (clang-2100.3.34.2) # go version go1.27.1 darwin/arm64 $ java Routes.java [4, 2, 2, 0, 0] $ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined routes.cpp -o routes && ./routes 4 2 2 0 0 $ go run routes.go [4 2 2 0 0]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 routes_session.py
All five print the same five answers. The differences between the languages are in the lookups:
- Python:
bisect_left(a, x)returns the first index whose value is at least x, andbisect_right(a, y)the first whose value is greater than y, sobisect_right(a, y) - bisect_left(a, x)counts the values from x to y.positions.get(code, [])reads a list without adding a key. With adefaultdict,positions[code]would add an empty list for every unknown code that a query names. - JavaScript has no binary search in its standard library, so
lowerBoundis written out. Called withlast + 1, it counts the positions at or beforelast, which is exact because positions are whole numbers. - Java builds the lists with
computeIfAbsentand reads them withgetOrDefault, which adds nothing. The library’sArrays.binarySearchmakes no promise about which index it finds when a value occurs more than once, so the code uses a lower bound written out, which behaves the same in every case. - C++ uses
std::upper_boundandstd::lower_boundfrom<algorithm>, and looks a code up withfind, becausepositions[code]would insert an empty list for an unknown code. - Go:
sort.SearchIntsreturns the lower bound, and reading a map with a missing key gives a nil slice, of length 0, without adding the key.
Why it is correct
The pass keeps one fact true, its invariant: after it has read scan i, the list of every code holds exactly the
positions up to i where that code occurs, in increasing order. It holds before the first scan, when every list is
empty, and each step appends to one list a position larger than every earlier one. So when the pass ends, the list of
code holds all of its positions, sorted.
For a sorted list, bisect_right(list, last) is the number of entries at or below last, which is the number of
parcels for code among scans 0 to last. bisect_left(list, first) is the number of entries below first, the
parcels for code among scans 0 to first − 1. The parcels before first are in both counts and cancel, so the
difference is the count from first to last. It is the subtraction of prefix counts, done on a list that stores
each count only where it changes. A code with no parcel has an empty list, and both searches return 0.
A dry run
from bisect import bisect_left, bisect_right
routes = [31, 58, 31, 31, 72, 58, 31]
queries = [(0, 6, 31), (1, 5, 58), (2, 3, 31), (4, 4, 58), (0, 6, 99)]
positions = {}
for i, code in enumerate(routes):
positions.setdefault(code, []).append(i)
print("positions:", positions)
for first, last, code in queries:
seen = positions.get(code, [])
up_to_last = bisect_right(seen, last) # how many positions are <= last
before_first = bisect_left(seen, first) # how many positions are < first
print(f"({first}, {last}, {code}) in {seen}: {up_to_last} at or before {last},"
f" {before_first} before {first}, so {up_to_last - before_first}")Output
positions: {31: [0, 2, 3, 6], 58: [1, 5], 72: [4]}
(0, 6, 31) in [0, 2, 3, 6]: 4 at or before 6, 0 before 0, so 4
(1, 5, 58) in [1, 5]: 2 at or before 5, 0 before 1, so 2
(2, 3, 31) in [0, 2, 3, 6]: 3 at or before 3, 1 before 2, so 2
(4, 4, 58) in [1, 5]: 1 at or before 4, 1 before 4, so 0
(0, 6, 99) in []: 0 at or before 6, 0 before 0, so 0
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 trace.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Route 31 is at scans 0, 2, 3 and 6. For (2, 3, 31), three of its positions are at or before 3 and one, scan 0, is before 2, which leaves scans 2 and 3. For (4, 4, 58), one position of route 58 is at or before 4 and one is before 4: the same one, scan 1, so the answer is 0.
The cost
| Operation | Time | Extra space |
|---|---|---|
| Brute force: count each stretch again | O(n × q) | O(1) |
| One prefix-count array per code | O(n × k + q) | O(n × k) |
| Sorted positions of each code, two binary searches a query | O(n + q log n) | O(n) |
At the limits, the index holds 200,000 positions, and each of the 200,000 queries makes at most about 2 × 18 comparisons in its two binary searches, about 7 million in all. Building the index is one pass, with one dictionary lookup and one append for each scan: O(1) on average for the dict and amortised O(1) for the list.
Check it against the brute force
The stress test runs both versions on 2,000 small random logs, from one scan up to ten, and stops at the first
disagreement, the habit from the lesson on brute force to optimal.
It also tries a plausible slip, bisect_left at both ends, and then runs the largest input the limits allow:
import random
from bisect import bisect_left
from brute import route_counts_slow
from routes import route_counts
def route_counts_slip(routes, queries):
"""A plausible slip: bisect_left at both ends, which leaves out a parcel exactly at last."""
positions = {}
for i, code in enumerate(routes):
positions.setdefault(code, []).append(i)
return [bisect_left(positions.get(code, []), last) - bisect_left(positions.get(code, []), first)
for first, last, code in queries]
def first_failure(candidate, cases=2_000, seed=30):
"""Runs candidate and the brute force on small random logs, shortest first, until they disagree."""
rng = random.Random(seed)
for case in range(cases):
n = 1 + case * 10 // cases # 1 to 10 parcels
routes = [rng.choice([5, 6, 7]) for _ in range(n)]
queries = []
for _ in range(3):
first = rng.randrange(n)
queries.append((first, rng.randrange(first, n), rng.choice([5, 6, 7, 8]))) # 8: a route with no parcel
got, expected = candidate(routes, queries), route_counts_slow(routes, queries)
if got != expected:
return f"fails on routes {routes}, queries {queries}: got {got}, expected {expected}"
return f"agrees with the brute force on {cases:,} random logs"
print("route_counts: ", first_failure(route_counts))
print("route_counts_slip:", first_failure(route_counts_slip))
# The largest input the limits allow: 200,000 parcels on 1,000 routes, and 200,000 queries.
rng = random.Random(7)
n = q = 200_000
routes = [rng.randint(1, 1000) * 1_000_003 for _ in range(n)]
queries = []
for _ in range(q):
first, last = sorted((rng.randrange(n), rng.randrange(n)))
queries.append((first, last, rng.randint(1, 1000) * 1_000_003))
answers = route_counts(routes, queries)
print(f"{n:,} parcels and {q:,} queries: {len(answers):,} answers, adding up to {sum(answers):,}")Output
route_counts: agrees with the brute force on 2,000 random logs route_counts_slip: fails on routes [5], queries [(0, 0, 8), (0, 0, 5), (0, 0, 6)]: got [0, 0, 0], expected [0, 1, 0] 200,000 parcels and 200,000 queries: 200,000 answers, adding up to 13,334,141
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 stress.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The positions version agrees with the brute force on all 2,000 logs. The slip fails on a log of a single parcel, for
route 5, and the query (0, 0, 5): bisect_left([0], 0) is 0, so the parcel exactly at last is left out. The last
line answers 200,000 queries over 200,000 scans; the counts add up to about 13 million because each of the 1,000
routes has about 200 parcels and a random stretch covers a third of the log.
Edge cases and common bugs
- A code that no parcel has gives an empty list and the answer 0. Answering it must not add the code to the index.
- A stretch of one scan,
first == last, gives 1 or 0. - The parcel exactly at
lastis counted bybisect_right(or by a lower bound oflast + 1) and left out bybisect_left, the slip above. - Scans numbered from 1 in the input: convert each query once, in the clarifying step, before writing any search.
- Codes given as text, such as
"NORTH-07": nothing changes, because a dictionary takes any hashable key.
Follow-up questions
Corrections move a parcel to another route between the queries. What changes? A correction moves one position
from the list of the old code to the list of the new one. In a Python list, bisect finds the place in O(log n), but
inserting or deleting shifts every later entry, O(k) for a list of k positions. That is fine for a few corrections and
slow for many on one busy route. With many corrections, a segment tree whose nodes count the codes in their range takes
each correction and each query in O(log n) dictionary steps, at O(n log n) memory. When every correction and query is
known in advance, a Fenwick tree for each code over the positions that code ever takes does the same in less memory.
The report wants the number of different routes from first to last instead. Does the index help? No, because
that question is about every code at once, not one. It is answered with all the queries known in advance, either by a
Fenwick tree that marks only the latest scan of each code seen so far, with the queries sorted by last, or by Mo’s
algorithm. In a coding round it is a hard problem; in contests it is a standard one.
Exercise
Exercise · Medium · Python
The k-th parcel of a route in a stretch of scans
The shift report now asks a second kind of question about the parcel log: within a stretch of scans, which parcel was the k-th one for a route? Write kth_parcel(routes, queries) in parcels.py.
routes[i]is the route code of the parcel scanned i-th, a whole number from 1 to 10⁹.- Each query is
(first, last, code, k), with0 <= first <= last < len(routes)andk >= 1. - For each query, return the scan position of the k-th parcel for route
codeamong the scansfirsttolast, counting from 1, or-1when those scans hold fewer thankparcels for that route. - Return the answers in the order of the queries.
kth_parcel([31, 58, 31, 31, 72, 58, 31], [(1, 6, 31, 2), (0, 6, 58, 3), (2, 2, 31, 1)])
# [3, -1, 2]There can be up to 200,000 scans and 200,000 queries, so walking through each stretch again is too slow. The sample tests check the example, a route that never appears, a k-th parcel exactly at last and one just past it, stretches of one scan, random small logs and a long log. The last test counts the items your function reads from routes and stops it once it has read more than twice the number of scans.
Starter code · parcels.py
def kth_parcel(routes, queries):
"""For each query (first, last, code, k): the scan position of the k-th parcel for route code among the scans
first to last, counting from 1, or -1 if those scans hold fewer than k parcels for that route."""
# Replace this line with your code.
return []The sample tests · test_parcels.py
import random
from parcels import kth_parcel
def trusted(routes, queries):
"""Answers the tests trust: walk through each stretch of scans and collect the route's parcels."""
out = []
for first, last, code, k in queries:
hits = [i for i in range(first, last + 1) if routes[i] == code]
out.append(hits[k - 1] if k <= len(hits) else -1)
return out
class Log(list):
"""A list of route codes that counts the items read from it, and stops a solution that reads too many."""
def __init__(self, values, limit):
super().__init__(values)
self.reads = 0
self.limit = limit
def _read(self, count):
self.reads += count
if self.reads > self.limit:
raise AssertionError(
f"too slow: more than {self.limit:,} items were read from a log of {len(self):,} scans; "
"build the positions of each route once and answer each query without reading the log again"
)
def __getitem__(self, index):
self._read(len(range(*index.indices(len(self)))) if isinstance(index, slice) else 1)
return super().__getitem__(index)
def __iter__(self):
for i in range(len(self)):
self._read(1)
yield super().__getitem__(i)
def test_prompt_example():
"""the example from the prompt"""
assert kth_parcel([31, 58, 31, 31, 72, 58, 31], [(1, 6, 31, 2), (0, 6, 58, 3), (2, 2, 31, 1)]) == [3, -1, 2]
def test_route_that_never_appears():
"""a code that no parcel has"""
assert kth_parcel([4, 4, 4], [(0, 2, 9, 1), (1, 1, 5, 1)]) == [-1, -1]
def test_kth_exactly_at_last():
"""the k-th parcel sits exactly at last, and the next one just past it"""
routes = [5, 6, 5, 5]
assert kth_parcel(routes, [(0, 2, 5, 2), (0, 2, 5, 3), (0, 3, 5, 3)]) == [2, -1, 3]
def test_stretches_of_one_scan():
"""first == last, with and without a parcel for the route"""
routes = [7, 8, 7]
assert kth_parcel(routes, [(1, 1, 8, 1), (1, 1, 7, 1), (2, 2, 7, 1), (2, 2, 7, 2)]) == [1, -1, 2, -1]
def test_counting_starts_at_first():
"""parcels before first do not count"""
routes = [3, 3, 3, 3]
assert kth_parcel(routes, [(2, 3, 3, 1), (2, 3, 3, 2), (2, 3, 3, 3), (0, 3, 3, 4)]) == [2, 3, -1, 3]
def test_random_small_logs():
"""300 random logs of up to 10 scans, against answers the tests trust"""
rng = random.Random(30)
for _ in range(300):
n = rng.randint(1, 10)
routes = [rng.choice([1, 2, 3]) for _ in range(n)]
queries = []
for _ in range(4):
first = rng.randrange(n)
queries.append((first, rng.randrange(first, n), rng.choice([1, 2, 3, 4]), rng.randint(1, 4)))
assert kth_parcel(routes, queries) == trusted(routes, queries), f"kth_parcel({routes}, {queries})"
def test_long_log_read_once():
"""20,000 scans and 20,000 queries, reading the log at most twice"""
rng = random.Random(8)
n = 20_000
codes = [rng.randint(1, 50) * 1_000_003 for _ in range(n)]
queries = []
for _ in range(20_000):
first = rng.randrange(n)
queries.append((first, rng.randrange(first, n), rng.randint(1, 50) * 1_000_003, rng.randint(1, 300)))
positions = {}
for i, code in enumerate(codes):
positions.setdefault(code, []).append(i)
expected = []
for first, last, code, k in queries:
later = [p for p in positions.get(code, []) if p >= first]
expected.append(later[k - 1] if k <= len(later) and later[k - 1] <= last else -1)
assert kth_parcel(Log(codes, limit=2 * n), queries) == expectedA hint
Build the index of the worked problem once: for every route code, the sorted list of the scan positions where it occurs. For a query, find where the first position at or after first sits in that list. How far after it is the k-th parcel, and what must you check before you return it?
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
10 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
How do you choose between prefix sums, a Fenwick tree, a segment tree and a sparse table for a range-query problem? Read the operation mix: what changes, and how the query combines values. If nothing changes and the query is a sum, a count or an XOR, use prefix sums: O(n) to build and O(1) a query. If nothing changes and it is a minimum, maximum, gcd, AND or OR, use a sparse table: O(n log n) to build and O(1) a query, because its two overlapping blocks do no harm for those. If single values change and the query is a sum, use a Fenwick tree, O(log n) for both. For any other associative combine with changes, or for changes to whole ranges, use a segment tree, with lazy tags for the range changes, at O(log n) each. Then check the sizes: at n = 10⁵ a sparse table holds about 1.6 million cells.
Why can a sparse table answer a range minimum in O(1) but not a range sum? It stores the answer for every block whose length is a power of two. For a range of length L it takes the largest power of two p that is at most L, and combines two blocks of length p: one that starts at the range’s first position and one that ends at its last. Together they cover the range, but they overlap whenever L is not a power of two. For a minimum the overlap does no harm, because min(x, x) = x, and the same holds for maximum, gcd, AND and OR. A sum would add the shared positions twice: for positions 1 to 6, covered by the blocks 1 to 4 and 3 to 6, positions 3 and 4 would count twice. Fixed data with sums takes prefix sums instead.
Key takeaways
- Two facts pick the structure: what changes and when, and how the answers for two parts of a range combine.
- Fixed data with sums or counts: prefix sums, O(1) a query. Fixed data with min, max or gcd: a sparse table, O(1) a query after an O(n log n) build.
- Changes to single values with sums: a Fenwick tree. Any other combine with changes, or changes to whole ranges: a segment tree, with lazy tags for the ranges. Both take O(log n) an operation.
- Changes that all come before the first question leave the data fixed: apply them, then treat it as static.
- Count before you choose: about 17 levels at n = 10⁵ for the trees, a third of the array for a brute-force query on average, and about 17 rows of n cells for a sparse table.
- Measured on the same 100,000 operations, the right structure beat the brute force by a wide margin in both CPython and C++.
- A question about one value inside a range is a prefix count stored where it changes: sorted positions and two binary searches.
- Square-root decomposition, Mo’s algorithm and persistent segment trees are contest tools. Read the operation mix again before reaching for one in a coding round.
References
- A New Data Structure for Cumulative Frequency Tables (P. M. Fenwick, Software: Practice and Experience 24(3), pages 327–336) (John Wiley & Sons)
- The LCA Problem Revisited (M. A. Bender and M. Farach-Colton, LATIN 2000, LNCS 1776, pages 88–94) (Springer)
- Competitive Programmer's Handbook (A. Laaksonen): chapter 9, Range queries; chapter 27, Square root algorithms; chapter 28, Segment trees revisited (CSES)
- bisect: Array bisection algorithm (The Python Standard Library) (Python Software Foundation)
- Time complexity of operations on built-in types (Python Software Foundation)
- time.process_time() (The Python Standard Library) (Python Software Foundation)
- Working Draft, Programming Languages: C++ (N4950): [lower.bound], [upper.bound] and [unord.map.elem] (ISO/IEC JTC1/SC22/WG21)
- Java SE 25 API: java.util.Arrays (binarySearch) (Oracle)
- Java SE 25 API: java.util.Map (computeIfAbsent, getOrDefault) (Oracle)
- Package sort: SearchInts (The Go Authors)
- The Go Programming Language Specification: Index expressions (The Go Authors)
- ECMAScript 2026 Language Specification: Map Objects (Ecma International)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress