Range-query data structures · HTML
st[k][i] summarizes length 2^k; answer a range with two possibly overlapping largest power-of-two blocks.
Recognition signals
- The array never changes after construction
- Query volume is very high
- The operation is idempotent
- O(n log n) preprocessing is affordable
- O(1) range queries are valuable
False friends
| Signal | Why it is different |
|---|
| Dynamic updates | One change invalidates many blocks; use a segment tree. |
| Overlapping blocks for range sum | Addition is not idempotent and double-counts overlap; use prefix sums. |
Core invariant
st[k][i] exactly summarizes [i,i+2^k), built from two adjacent half-length blocks.
State, transition, and processing order
| Item | Definition |
|---|
| State | A two-dimensional st table and a floor-log table indexed by interval length. |
| Transition | Build from short blocks to long; query with k=floor(log2(r-l)) and merge the leading and trailing 2^k blocks. |
| Frontier / order | Construction advances by block length; queries jump directly to two blocks and have no dynamic frontier. |
Python skeleton
class SparseTableMin:
def __init__(self, a):
n = len(a)
self.log = [0] * (n + 1)
for i in range(2, n + 1): self.log[i] = self.log[i//2] + 1
self.st = [a[:]]
k = 1
while 1 << k <= n:
h = 1 << (k-1)
row = [min(self.st[k-1][i], self.st[k-1][i+h])
for i in range(n-(1<<k)+1)]
self.st.append(row); k += 1
def query(self, l, r):
k = self.log[r-l]
return min(self.st[k][l], self.st[k][r-(1<<k)])
Correctness sketch
- Level zero has correct singleton summaries.
- Two correct half-blocks produce a correct double-length block.
- The selected leading and trailing blocks cover the entire query without leaving it.
- Idempotence makes duplicated overlap harmless.
Complexity
| Time | Space | Parameters |
|---|
| O(n log n) preprocessing and O(1) query | O(n log n) | n array length; Q queries cost O(n log n+Q) total |
Edge cases
- Queries must be nonempty
- n=1 has only level zero
- Power-of-two lengths make both blocks coincide
- Negative values are fine for min/max
- Index answers need a tie rule
Error patterns
| Pattern | Why it fails / fix |
|---|
| Confusing associativity with idempotence | The overlapping O(1) trick also requires f(x,x)=x. |
| Taking log of an endpoint | Use the interval length r-l. |
| Wrong trailing-block start | It is r-2^k. |
Selection and exclusion rules
- Static min/max/gcd with many queries: Sparse Table.
- Static range sums: prefix sums.
- Any updates: segment tree or Fenwick.
- Few queries: avoid disproportionate preprocessing.
Original micro-example
| Part | Detail |
|---|
| Result | Merge blocks [1,5) and [2,6) to get 2. |
| Scenario | Query the minimum on [1,6) of static [6,3,8,2,7,5]. |
| Walkthrough | The blocks overlap, but repeated inputs do not affect min. |
Recall prompts
My notes