Data Structures19 sections · 729 units
Open in Course

RMQ to LCA Reduction

The reverse direction

I showed LCA reduces to RMQ (via Euler tour). The reverse is also true: RMQ reduces to LCA.

Given an array, build a Cartesian tree where each node's value is the minimum of its subtree.

Then RMQ(l,r)\text{RMQ}(l, r) equals the value at LCA(nodel,noder)\text{LCA}(\text{node}_l, \text{node}_r). Why care?

Some LCA structures (like binary lifting) are simpler to implement than sparse tables. Also, this connection is theoretically interesting: RMQ and LCA are equivalent problems. Any O(n)O(n) preprocessing, O(1)O(1) query solution for one gives the same for the other.