§ Cartesian Trees
Cartesian trees construct a tree T=C(A) given an array A, such that
range minimum query (RMQ) on the array A is equivalent to the lowest common ancestor (LCA)
of the nodes of the tree T.
Note that the tree looks like a min-heap .
To see the connection to LCA, if we want to find the range minimum in the range containing the
elements [12, 10, 20, 15, 18] of the array, the minimum is 10, which is
indeed the lowest common ancestor of the nodes of 12 and 18 in the tree.
§ Building a Cartesian tree in linear time:
§ Converting LCA to RMQ
We can go the other way, and convert an LCA problem into a RMQ problem. We
perform an inorder traversal of the nodes, scribbling down the
depth of the node ( Link to lecture at 15:30 ).
We ask for the argmin version of RMQ, that gives us the index of
the node with the lowest depth. This gives us the index of where the node lives.
§ Universe reduction in RMQ
We can have an arbitrary ordered universe, on which we want to perform RMQ.
We can convert this to LCA by using a cartesian tree, and then convert to
a "clean" RMQ (by using the LCA -> RMQ using depth conversion). This now
will give us way faster operations (since we now have integers).
§ +-1 RMQ:
We want the differences between nodes to have a difference of only +-1. We
had a much wider gap. Here, we perform an Euler tour (walk the tree DFS search order),
and sribble down every vertex we visit.
To find the LCA, we perform the RMQ on the locations of the first occurence
of the node. (I think we don't actually need the first occurence, any
occurence will do).
§ References
