main page — CS 566 Efficient Algorithms
Unit 14: Range-Minimum Queries
This is an archived version of this module from Winter 2024-25.
This unit covers the range-minimum query (RMQ) problem:
- trivial solutions, sparse table
- longest common extensions in strings and RMQ
- linear-time preprocessing via exhaustive tabulation
Learning outcomes
- Know the RMQ problem and its connection to longest common extensions in strings.
- Know and understand trivial RMQ solutions and sparse tables.
- Know and understand the Cartesian trees data structure.
- Know and understand the exhaustive-tabulation technique for RMQ with linear-time preprocessing.
Material
- slides
- Video 14-1 (2025-02-10):
§14.1 RMQ introduction
- Video 14-2 (2025-02-10):
§14.2 LCE using RMQ
- Video 14-3 (2025-02-10):
§14.3 Primitive RMQ & Sparse Tables
- Video 14-4 (2025-02-10):
§14.4 Cartesian trees
- Video 14-5 (2025-02-10):
§14.5 Exhaustive tabulation
Further reading and sources
The presentation is based on own work. It takes inspiration from the following paper on the related level-ancestor problem:
A more detailed exposition (with slightly different codes for the lookup table) appears here: