Range Add, Range Max — Solution & Editorial

Back to the Problem

Lazy propagation: store pending add-values on internal nodes and push them down on demand; both operations become O(log N).

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