Update Operation

To update node $v$ to value $x$, follow these steps: Find the chain $v$ belongs to with c = chain[v]. Find the position in the chain with p = pos[v]. Update the segment tree at position $p$ to value $x$. This takes $O(\log n)$ time per update, the same as a standard segment tree update.

The update propagates up the segment tree to maintain range maximums. Updates are fast because each node has a fixed position in the segment tree. You do not need to rebuild any structure.

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