To update node to value , follow these steps: Find the chain belongs to with c = chain[v]. Find the position in the chain with p = pos[v]. Update the segment tree at position to value . This takes 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 for the data structures used.