For an update query , find pos[s], the position of node in the flattened array. Update the segment tree at that position to . Since belongs to exactly one chain, this is a single segment tree point update. The update takes time, touching 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 for the data structures used.