Range Add, Range Sum — 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)

Watch out: A pending add applies to a whole subtree: sum changes by v·(segment length) — the classic lazy detail.