main page  —  COMP 526 Applied Algorithmics

Unit 9: Range-Minimum Queries

This is an archived version of this module from Spring 2020.
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 “Four-Russian” tables


  • lecture notes
  • slides
  • Lecture 2020-04-27: Intro + LCE application

  • Lecture 2020-04-27: Sparse tables

  • Lecture 2020-04-27: Cartesian trees (part 1)

  • Lecture 2020-04-28: Cartesian trees (part 2)

  • Lecture 2020-04-28: “Four Russians” Table

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: