So it uses the same alg as in the paper; but you calculate the cartesian tree of the array, then the index of RMQ of [le, ri] is the LCA of nodes le, ri in the cartesian tree.

So the paper describes how to calculate 3 arrays INLABEL, ASCENDANT, HEAD from a rooted tree; and then how to answer O(1) LCA using these arrays. I thought the paper describes the alg quite well, so I won't re-explain it here. But I can mention a few key points:

So our task is to calculate these arrays INLABEL, ASCENDANT, HEAD from the cartesian tree of the array.

For a node u, the paper defines INLABEL[u] as (considering all nodes in u's subtree) the dfs-time-in value with maximum count of trailing zeros (__builtin_ctz) in it's binary representation.

And noting, among the numbers le, le+1, ..., ri-1, ri, the number with maximum count of trailing zeros is given by ri & -bit_floor(ri^(le-1)).

So we could calculate dfs-time-in of cartesian tree, then use the above formula with: le = time_in[u], ri = time_in[u]+subtree_size[u]-1; but there's a better way:

the paper has this remark:

Remark: The above computation is based on PREORDER numbering of the vertices of T. This numbering has the property that the numbers assigned to the subtree rooted at any vertex of T provide a consecutive series of integers. In fact, any alternative numbering having this property (e.g. POSTORDER, INORDER) will produce INLABEL numbers which will be suitable for our preprocessing stage.

And for cartesian tree, It makes more sense to calculate INLABEL over INORDER traversial instead of PREORDER, because the INORDER value of node u is just u.

And for cartesian tree, the INORDER values of the subtree of u is the range [index_of_previous_smaller[u]+1, index_of_next_smaller[u]-1], where the previous and next smaller indexes can be calculated with the monotonic stack alg.

Finally one more point is I don't actually build the cartesian tree, rather it is thought of as being "implicitly" used; just like for rectangular-array-graph problems, where you just loop over the 4 (or 8) neighbors "implicitly" in a loop instead of building the graph "explicitly"

So if you take the code:

vector<int> st;
for(int i = 0; i < n; i++) {
  int prev = -1;
  while(!empty(st) && a[st.back()] > a[i]) {
    // (1)
    prev = st.back();
    st.pop_back();
  }
  // (2)
  st.push_back(i);
}

It's kind of like doing an "implicit" dfs on cartesian tree: the order which nodes are popped off the stack is POSTORDER of cartesian tree for example. Also there's a bunch of invariants:

at spot 1, we have:

• index_of_previous_smaller[prev] == st.back()
• index_of_next_smaller[prev] == i
• parent of prev in cartesian tree == st.back()

at spot 2, we have:

• index_of_previous_smaller[prev] == st.back()
• index_of_next_smaller[prev] == i
• parent of prev in cartesian tree == i

One more thing which may help: as you pop off the stack, it's like looping up the "right-spine" of the cartesian tree: