Path Queries II - Update Algorithm

For an update query $(s, x)$, find pos[s], the position of node $s$ in the flattened array. Update the segment tree at that position to $x$. Since $s$ belongs to exactly one chain, this is a single segment tree point update. The update takes $O(\log n)$ time, touching $O(\log n)$ nodes in the segment tree.

The segment tree automatically propagates the change up to maintain range maximums. You do not need to update anything else manually. The chain structure remains unchanged.

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