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.

Material

• slides

• lecture notes

• Video 9-1 (2022-04-25): §9.1 RMQ introduction

• Video 9-2 (2022-04-25): §9.2 LCE using RMQ

• Video 9-3 (2022-04-25): §9.3 Primitive RMQ & Sparse Tables

• Video 9-4 (2022-04-25): §9.4 Cartesian trees

• Video 9-5 (2022-04-28): §9.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:

• 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

---

Unit 8  ⋅  Syllabus