Algorithms and Data Structures · Senior · Question 71 of 75
What does the "sparse table" structure answer in O(1)?
- ✓Correct answer: Range minimum queries on a static array
- 2Membership checks in a dynamic set of keys
- 3Shortest paths between any two of the vertices
Explanation
It precomputes minimums of all ranges of length 2ᵏ in O(n log n). Any range is covered by two overlapping power-of-two ranges, and min doesn't care about overlap. Updates would require rebuilding.