main page — CS 566 Efficient Algorithms
Unit 15: 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
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: