Expert · Module 26 · Lesson 1 of 4
Sparse tables
Precompute every power-of-two range once, then answer a minimum, maximum or gcd over any slice with two array reads. The trick survives only if the operation tolerates overlap.
By the end you can
- Explain how the doubling table stores every power-of-two range and why it costs O(n log n) memory
- Answer a range minimum query with two overlapping blocks and name the property that makes it correct
- Say why sums and updates break the design, and name a structure for each
Builds on Prefix sums.
01 · A question first
Prefix sums answer any range sum in constant time, but they do not work for minimums: you cannot subtract a minimum. You want the minimum of any slice of an array that never changes, faster than a scan. There is a table that answers it with two array reads, and a hidden condition on which operations it may hold.
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- The query a prefix sum cannot answer
- A row for every power of two
- One query, two overlapping blocks
- Why the overlap is allowed
- What a query cannot do: updates
- Where it is used
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem