Our last lecture took us very, very close to a $\langle O(n), O(1) \rangle$-time solution to RMQ. Using a new data structure called a Cartesian tree in conjunction with a technique called the Method of Four Russians, we can adapt our approach to end up with a linear-preprocessing-time, constant-query-time solution to RMQ. In doing so, we'll see a number of clever techniques that will appear time and time again in data structure design.
Readings
- Johannes Fischer and Volker Heun. Theoretical and Practical Improvements on the RMQ-Problem with Applications to LCA and LCE
Links