Segment Tree per Chain

Build one segment tree for each chain. The segment tree for chain $c$ has size equal to the number of nodes in that chain. Position $i$ in the segment tree stores the value of the node with pos[v] = i in chain $c$. You can query the maximum in a range $[l, r]$ in $O(\log n)$ time using standard segment tree queries.

Since the tree has $n$ nodes total across all chains, the total space is $O(n)$ for all segment trees combined. Each node belongs to exactly one chain, so the segment tree sizes add up to $n$.

Space complexity is $O(n)$ for the data structures used.