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

Material

• 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:

• Bender & Farach-Colton: The Level Ancestor Problem simplified (2004), Theoretical Computer Science, 321(1), 5–12.

A more detailed exposition (with slightly different codes for the lookup table) appears here:

• Ohlebusch: Bioinformatics algorithms (2013) Oldenbusch Verlag