Path Queries II - Segment Tree

Build a segment tree of size $n$. For each node $v$, place val[v] at index pos[v] in the segment tree. This flattens the tree into a linear array. The segment tree supports $update(p, x)$ to set position $p$ to value $x$, and $query(l, r)$ to return the maximum in range $[l, r]$.

Both operations take $O(\log n)$ time. Initialize the segment tree with the initial node values. Each node's value goes at its flattened position. The segment tree maintains range maximums at internal nodes.

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