Advanced · Module 19 · Lesson 6
Sparse table
Static idempotent range queries.
15–25 min readLesson 120 of 123
Lesson 120 of 123
1d streakTheory lesson · Step-by-step
Understand Sparse table
Static idempotent range queries.
Worked approach
Trace the reasoning step by step
- 1Precompute powers of two.
- 2Build each level from two half ranges.
- 3Decompose a query or overlap two blocks for idempotent operations.
- 4Use only for static data.
Concrete example
Query minimum on a static range of length 6.
- 1Choose k=floor(log₂6)=2.
- 2Use two overlapping blocks of length 4.
For idempotent min, combining both block minima gives the answer.
What must remain true (Loop Invariant)
table[k][i] stores the answer for the length-2ᵏ range starting at i.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Range operation
O(1) idempotent query, O(n log n) build
O(n log n)
Choose based on update/query balance and operation properties.When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked Sparse table example without looking at the trace.
- Change one input condition and explain whether the Sparse table invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.