Stacked Range Additions — Solution & Editorial

Back to the Problem

Difference array: +V at L and −V at R+1 per update, then one prefix-sum pass — O(1) per update instead of O(length).

Complexity: O(N + M)

Watch out: Applying each update literally is O(NM) = 10¹⁰ — the whole problem is the difference-array trick.