Point Assign, Range Max — Solution & Editorial

Back to the Problem

A max segment tree supports point assignment and range-max in O(log N) each (iterative bottom-up implementation shown).

Complexity: O((N + Q) log N)