Sparse tables for immutable range minimum queries

A sparse table answers an immutable range-minimum query by combining two precomputed power-of-two blocks. The blocks may overlap because repeating a value does not change a minimum. For a student deciding between prefix sums, segment trees, and sparse tables, that overlap rule explains why the same constant-time query formula fails for sums.

Use values [5, 2, 7, 1, 3, 6, 0, 4] and query the half-open interval [1, 6). It contains five values: two, seven, one, three, and six. The largest power of two no greater than five is four. Use the four-value block beginning at one and the four-value block ending at six. Array indexing, integer powers of two and the minimum operation are enough to follow the construction.

Precompute intervals of doubling length

Table level zero stores individual values. Level one stores minima over length two, level two over length four, and so on. A length-2^k interval splits into two adjacent length-2^(k - 1) intervals, so each entry combines two entries from the preceding level.

class SparseMin:
    def __init__(self, values):
        values = list(values)
        self.n = len(values)
        self.table = [values]
        width = 2
        while width <= self.n:
            half = width // 2
            previous = self.table[-1]
            row = [min(previous[i], previous[i + half])
                   for i in range(self.n - width + 1)]
            self.table.append(row)
            width *= 2

    def query(self, left, right):
        if (type(left) is not int or type(right) is not int
                or not 0 <= left < right <= self.n):
            raise IndexError('expected a nonempty half-open interval')
        length = right - left
        level = length.bit_length() - 1
        width = 1 << level
        return min(self.table[level][left], self.table[level][right - width])

values = [5, 2, 7, 1, 3, 6, 0, 4]
ranges = SparseMin(values)
assert ranges.table[2] == [1, 1, 1, 0, 0]
assert ranges.query(1, 6) == 1
assert ranges.query(6, 7) == 0
assert ranges.query(0, 8) == 0

Rows shorten because an interval must fit entirely inside the input. At length four, eight values allow five starting positions. The query chooses its level with the integer bit length of the positive interval length, avoiding floating-point logarithm rounding near powers of two.

The class rejects empty queries. A minimum over an empty interval has no ordinary member value, so this API reports an invalid range rather than introducing an infinity sentinel. An empty source can be constructed but has no valid nonempty query.

View full-size image ↗

For the example, block [1, 5) contains 2, 7, 1, 3 and block [2, 6) contains 7, 1, 3, 6. Both have minimum one. Their union is exactly the requested interval, even though the middle three values appear in both blocks.

Overlap is safe because minimum is idempotent

Let the query length be L and chosen block width be w, with w <= L < 2w. The first block covers the left w positions and the second covers the right w positions. Because L < 2w, the blocks overlap, leaving no uncovered gap. If L = w, they are exactly the same block. Neither block extends beyond the query.

The minimum of their two minima is therefore the minimum over the union. A value present in both blocks is considered twice, but min(x, x) = x. This property is called idempotence. It is the extra condition that permits overlapping aggregates in this query method.

Associativity alone would allow regrouping disjoint segments but would not justify counting overlapping segments twice. CP-Algorithms’ sparse-table explanation distinguishes the constant-time range-minimum query from operations that cannot use the same overlap shortcut.

Apply the same blocks to sums and see the error

The sum of [1, 5) in the example is thirteen, and the sum of [2, 6) is seventeen. Adding them gives thirty. The requested interval [1, 6) actually sums to nineteen. The difference, eleven, is exactly the repeated overlap 7 + 1 + 3.

No indexing adjustment inside min was responsible for the valid minimum result. The aggregate’s behavior made duplication harmless. Replacing min with addition in the two-block query changes that behavior and invalidates the proof.

A standard sparse table can answer a sum query by decomposing the range into disjoint power-of-two blocks, which takes O(log n) selected blocks. For immutable sums, an ordinary prefix array usually provides a simpler O(n) preprocessing and O(1) query solution. A disjoint sparse table is another structure with different preprocessing and query reasoning; it should not be confused with the overlapping construction here.

Pay the preprocessing cost only when it fits

There are O(log n) levels, each containing at most n entries, so construction and storage cost O(n log n). A valid minimum query reads two entries and performs one min, giving O(1) work under a bounded-word index model. The time spent building the table is worthwhile when many queries reuse the same values.

A point change invalidates many stored intervals that contain that position. This class has no update method and rebuilds the table when data changes, costing O(n log n). For frequent changes, a segment tree supports logarithmic updates and range queries; the AtCoder segment-tree interface makes that tradeoff explicit.

Memory can decide the choice before query speed does. An input that fits in one array may not fit after storing several levels of reference or numeric arrays. Estimate the actual element representation and level count, then compare with a segment tree or another range-minimum structure suitable for the workload.

Test every nonempty interval of a short array against a direct minimum. Include lengths exactly equal to powers of two and one greater than a power of two, where the overlap pattern changes. Repeated minima and a minimum just outside the query catch accidental overreach. This implementation captures a finite iterable once and copies its references, so replacing a caller’s list entries cannot update the table. Referenced values themselves must remain immutable and totally ordered; a shallow list copy does not freeze mutable objects. Exclude floating-point NaN, whose comparisons do not provide the order needed by this minimum proof.

Return the position of a minimum with a stable tie rule

A chart may need to highlight the earliest lowest sample, not merely print its value. Store each sample together with its original position: (value, index). Python compares tuples lexicographically, so their minimum first selects the smallest value and then the smallest index. Applying min to these pairs remains associative and idempotent. The same overlapping query proof still applies, including when an identical pair appears in both blocks.

samples = [4, 1, 1, 5, 1]
positions = SparseMin((value, index)
                      for index, value in enumerate(samples))
assert positions.query(1, 5) == (1, 1)
assert positions.query(2, 5) == (1, 2)
assert positions.query(3, 4) == (5, 3)
samples[1] = 9
assert positions.query(1, 5) == (1, 1)
rebuilt = SparseMin((value, index)
                    for index, value in enumerate(samples))
assert rebuilt.query(1, 5) == (1, 2)

In [1, 5), positions one, two and four all contain one, and the first pair wins. Moving the left boundary to two removes the earlier candidate without changing the policy. Replacing samples[1] afterward does not alter the existing index: its value-index tuples are already captured. Rebuilding selects position two under the new input. This distinction matters when a user edits chart data but an application keeps its old query structure alive.

View full-size image ↗

The tie rule belongs in the aggregate, not in whichever block happens to be queried first. For a latest-position policy, compare (value, -index) and recover the original index by negating the second field. State the choice in the interface; both policies return the same numeric minimum but can highlight different samples. Tuple comparison here examines at most two fields, under the same constant-cost value comparison assumption as the numeric version.

The exact table size helps make the space tradeoff concrete. For eight values, the valid row lengths are eight, seven, five and one, totaling twenty-one stored entries. A hypothetical change at position three affects one singleton, two length-two intervals, four length-four intervals and the single length-eight interval. Eight cached answers may need repair, while a segment tree changes one ancestor per level. A specialized repair need not rebuild every entry, but this static class deliberately offers only reconstruction; do not infer logarithmic update cost from its logarithmic number of levels.

As an exercise, use the five-sample fixture to test every interval against min((samples[i], i) for i in range(left, right)). Repeat after an edit by building a fresh table, and implement the latest-position policy. Include a range whose only lowest sample lies just outside its left boundary. That case distinguishes a valid tie policy from an incorrectly extended query.