main page  —  COMP 526 Applied Algorithmics

Unit 9: Range-Minimum Queries

This is an archived version of this module from Spring 2022.
Click here for the current iteration.

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

  1. Know the RMQ problem and its connection to longest common extensions in strings.
  2. Know and understand trivial RMQ solutions and sparse tables.
  3. Know and understand the Cartesian trees data structure.
  4. Know and understand the exhaustive-tabulation technique for RMQ with linear-time preprocessing.


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:

Unit 8  ⋅  Syllabus