Unit 9: Range-Minimum Queries

This is an archived version of this module from Spring 2021.
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

• slides (preliminary)

• lecture notes

• Video 9-1 · transcript (2021-05-04, 15:01): §9.1 RMQ introduction
  
  Chapters

  0:53 Overview
  1:50 RMQ problem
  8:47 Commentary
  11:59 Random guesses
  
• Video 9-2 · transcript (2021-05-04, 13:08): §9.2 LCE using RMQ
  
• Video 9-3 · transcript (2021-05-04, 3:54): §9.3 Primitive RMQ solutions
  
• Video 9-4 · transcript (2021-05-05, 12:44): §9.3 Sparse table RMQ
  
• Video 9-5 · transcript (2021-05-05, 37:33): §9.4 Cartesian trees
  
  Chapters

  4:33 Defining Cartesian trees
  8:14 RMQ and tree traversal
  14:15 Cartesian tree exercise
  22:53 Visualizing tree structures
  26:44 Encoding binary trees
  
• Video 9-6 · transcript (2021-05-05, 21:29): §9.5 Four Russians lookup table
  
  Chapters

  2:00 Simple solution
  6:22 Rangeman query
  16:05 Preprocessing
  19:45 Conclusion
  

---

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