Static intervals and a different tradeoff
A segment tree can support updates, but a fixed array allows preprocessing that answers a minimum query with two stored values. We develop the table and its assumptions before comparing costs.
Let be an unchanged array of values from a totally ordered set. Queries use inclusive indices . We count each comparison and array access as constant time and assume table indices and a precomputed logarithm fit in the machine's word model.
Definition 2.1.1
(Sparse table entries)
For every with and valid start , define
There are exactly valid entries in row . We store no entry for an interval extending past the array.
Building the invariant
Theorem 2.1.2
(Power-of-two intervals)
The table is built by and, for ,
Every valid entry then equals the minimum on its stated interval.
Proof
(Induction on the row index)
The base row stores each length-one interval. A valid length- interval splits into two disjoint length- intervals at the displayed starts. Both entries exist because the whole interval fits. By induction they store the two minima, whose minimum is the minimum of the union. ∎
The build has rows and at most entries per row: time and storage are . A table of for can be built in time by and for .
Answering with overlapping blocks
Theorem 2.1.3
(Two-block query)
Let , , and . Then and both exist, and .
Proof
(Two covering blocks)
For a query let , and . Then . The length- intervals and lie inside and cover it, possibly overlapping. Therefore
An index lying in both blocks is considered twice, but , so the minimum is unchanged. When the two blocks coincide, which is also valid.
Proof X-ray
The two inequalities that make the blocks work
Two inequalities decide everything. The blocks fit inside because , which is why both stored entries exist and contain no outside element. They cover because : the right block starts at , no later than the last index of the left block, so no index is missed. With a smaller a gap would remain, and with a larger a block would stick out; is the unique choice meeting both. Idempotence is needed only for the nonempty overlap that the second inequality guarantees.
With the precomputed logarithm, the query requires two lookups and one comparison: in the stated model. This is a static-array guarantee; an assignment can invalidate many entries. Rebuilding the whole table is a simple valid response, but a segment tree is designed to handle point assignments without rebuilding.
Common mistake
(Rounding the logarithm up)
Taking gives , with unless is a power of two. For the block length would be , longer than the query, so the block contains elements outside and the stored entry may not exist. The floor is forced by the requirement that each block lie inside the query.
Common mistake
(Off by one in the second block)
The second block starts at , not at . In the six-value example below, the query has ; starting at repeats the block and returns , missing the value at index .
Worked example 2.1.4
(A six-value array)
Take . Row zero is the array; row one is and row two is . For , the length is five and . The left block has minimum , the right block has minimum , so the query returns . Their overlap is harmless for minimum.
Worked example 2.1.5
(A query that is exactly one block)
Use again. For the query we have , , , and both blocks are : the formula reads , the minimum of and . For the singleton query we have , , , and the formula reads . In both cases the two blocks coincide, and idempotence returns the stored value unchanged.
Worked example 2.1.6
(Building rows by doubling and answering a query)
Let , so . Row one has seven entries, . Row two combines entries two apart: , , , and , giving . Row three has the single entry . For the query we have , , ; the blocks are and with stored minima and . The answer is , which matches the direct minimum of .
Counterexample mode
A stale table
After building the table for the six-value array , change from to without updating the table. The old query still returns , although the new minimum of is . The invariant applies to the array used at build time; an assignment requires the stored data to be updated or rebuilt.
Associativity and idempotence explain why overlap is safe
Definition 2.1.7
(The relevant algebraic properties)
For a binary operation on a value domain, associativity means
and idempotence means . An interval aggregate combines its entries in their original left-to-right order.
Minimum is associative and idempotent. Maximum, greatest common divisor on positive integers, and bitwise AND or OR also have these properties on their usual domains. Addition is associative but not idempotent.
Proposition 2.1.8
(Overlapping blocks are safe)
Let be associative and idempotent. Suppose a queried sequence is the concatenation of consecutive pieces with nonempty, and write also for their aggregates, omitting an empty outer piece. If one stored block aggregates and the other aggregates , then .
Proof
(Regroup, then absorb the overlap)
Write the queried sequence as three consecutive pieces , where is the nonempty overlap. The first stored block aggregates , and the second aggregates .
Associativity lets their combination be grouped as
where the letters in this formula denote their respective piece aggregates, and the second equality uses idempotence of the overlap aggregate. If an outer piece is empty, omit it; the overlap itself is still nonempty. In the coincident-block case, the formula is simply .
Proof X-ray
Where each hypothesis acts
The proof has two moves. First, associativity regroups the four factors without moving any of them. Second, idempotence collapses ; this is the only step that uses it, and it applies to the aggregate of the overlap, not to single elements of or . Dropping either hypothesis breaks a different step, as the two counterexamples after this block show: sums fail the second move, and the averaging operation fails the first.
The order of different pieces never changes, so commutativity is unnecessary for this argument. Associativity justifies grouping blocks; idempotence removes the repeated overlap. Both roles matter.
Each hypothesis can be removed separately, and each removal gives a concrete wrong answer.
Counterexample mode
Using the two blocks for sums counts the overlap twice
Take [3, 1, 4, 1, 5, 9, 2] and query [1, 5]. The length is five, so use blocks [1, 4] and [2, 5]. Their sums are 11 and 19, giving 30 if simply added.
The actual range sum is 20. The overlap [2, 4] sums to 10 and was counted twice. Addition preserves grouping, but it cannot erase repeated data. Even when a query is exactly one power-of-two block, adding that same block to itself would double its sum.
The converse failure is also real: idempotence cannot compensate for a missing grouping property.
Counterexample mode
Idempotence alone does not make an arbitrary aggregate valid
The operation is idempotent, but it is not associative: , while .
For array [0, 0, 6], the two length-two block means are 0 and 3. Averaging them gives , while the full range mean is 2. Calling an operation idempotent is insufficient when the block-grouping step itself lacks its required algebraic property.
For an associative operation without idempotence, an ordinary sparse table can still answer by a disjoint decomposition. A length-13 interval, for example, can be split left to right into lengths . The binary expansion gives at most blocks, so this query method takes combinations. Preserve their left-to-right order for noncommutative operations; start with the first block if no identity element is available. This establishes a valid alternative query method without claiming the overlapping formula works. Sums also have the simpler prefix-sum solution when subtraction is available.
An implementation with integer logarithms
The class takes a snapshot of a nonempty input sequence. Its rows contain only valid block starts. A precomputed integer-log table avoids floating-point logarithms at query time. The values must have a total order; the examples use integers.
class SparseMin:
def __init__(self, values):
base = list(values)
if not base:
raise ValueError("sparse table requires a nonempty array")
self.n = len(base)
self.logs = [0] * (self.n + 1)
for length in range(2, self.n + 1):
self.logs[length] = self.logs[length // 2] + 1
self.table = [base]
span = 2
while span <= self.n:
half = span // 2
previous = self.table[-1]
row = [min(previous[i], previous[i + half])
for i in range(self.n - span + 1)]
self.table.append(row)
span *= 2
def query(self, left, right):
if not 0 <= left <= right < self.n:
raise IndexError("query must be a nonempty in-bounds interval")
k = self.logs[right - left + 1]
span = 1 << k
return min(self.table[k][left],
self.table[k][right - span + 1])
The two queried entries always exist: each chosen block fits inside the valid query interval. A singleton query uses row zero and combines the same value twice. For the worked array, SparseMin(values).query(1, 5) returns 1. Preprocessing and storage take ; each query takes in the standard model of constant-time index and value operations.
A logarithmic number of rows does not give logarithmic updates
Changing array position can affect many blocks in the same row. At block length , every valid start with may need recomputation. There are at most such starts. Summing over levels gives fewer than potentially affected entries, but that is a linear, not logarithmic, bound.
The worst case really is linear for an explicitly maintained table. Let be a power of two, choose zero-based position , and begin with all values one. Change that value to zero. At the row of block length , the blocks starting at all contain the changed point, and every stored minimum changes.
Thus even updating only the affected entries can require work. Rebuilding all rows costs . The displayed class supplies static queries and no update method. A setting with frequent updates requires a data-structure choice matched to that interface, such as the course's segment-tree topic.
Return the leftmost minimum by storing enough information
If a query needs a minimum's position, store pairs and compare them lexicographically. The smaller value wins; equal values choose the smaller index. Taking the minimum of these pairs remains associative and idempotent, so every earlier proof still applies.
For [4, 1, 3, 1, 2], the pair minimum over [0, 4] is , identifying the leftmost minimum rather than the equal value at index 3. The same class supports this representation by receiving [(value, index) for index, value in enumerate(values)]. Storing only minimum values would have discarded the positional information.
Exercises
Quick check
(For , build rows zero, one and two of the minimum table.)
Row combines two entries of row that are apart.
Solution · Answer
The rows are , and .
Quick check
(Using that table, answer the query and identify the two queried blocks.)
Compute , then and .
Solution · Answer
The length is three, so . The blocks and have minima and ; the answer is .
Quick check
(Why can an interval of length exactly be queried using the same block twice?)
What are the two blocks when ?
Solution · Answer
Both blocks equal the whole range, and .
Quick check
(Let . How many rows does the table have, how many entries are in the last row, and what are the build, storage and query bounds?)
The largest with gives the last row.
Solution · Answer
Since , the rows are , which is rows. The last row has entries. Build and storage are ; a query is with a precomputed logarithm table and constant-time access and comparison.
Further reading
Algorithms for Competitive Programming: Sparse Table describes power-of-two range tables.