721. Many Range Increments, One Pass
An array of n zeros is given. Then q updates arrive, each l r v, meaning "add v to
every position from l to r inclusive", with positions numbered from 1.
Print the final array.
n = 5, updates (1 3 2) and (2 5 3) -> 2 5 5 3 3
n = 3, updates (1 1 1) (1 2 1) (1 3 1) -> 3 2 1
## Why the obvious loop is too slow
Walking each range costs the length of the range, so q updates over an array of n cost
O(n q). With both at 2 * 10^5 that is 4 * 10^10 operations.
## Record the CHANGES, not the values
Keep a second array d, where d[i] is how much position i differs from position i - 1.
Adding v across l .. r changes exactly two of those differences:
d[l] += v the step up at the start of the range
d[r + 1] -= v the step back down just after it
Everything strictly inside the range is unchanged, because both its neighbours moved by the
same v. So each update is TWO writes regardless of how wide it is.
At the end, one running total recovers the array:
run = 0
for i in 1 .. n:
run += d[i]
a[i] = run
## This is the prefix sum run backwards
A prefix sum turns an array into its running totals so a range query is one subtraction. A difference array turns an array into its steps so a range UPDATE is one subtraction. They are inverse operations, and recognising which direction a problem needs is the skill this whole block is about.
## The r + 1 that must exist
When r is n, the write lands at index n + 1. That position is never read back, but it
must be allocatable, so the array is sized n + 2 rather than n.
Sizing it n and guarding the write with an if also works. Sizing it n and NOT guarding
is the crash, and it only happens on inputs whose last update reaches the end.
## Where this already appears in the bank
Problem 1439 asks whether a vehicle ever exceeds its capacity given boardings and departures along a route. That is this technique with the array indexed by position along the route rather than by array slot, and it is worth reading beside this one once the machinery is clear.
## Overflow
2 * 10^5 updates of 10^9 stack to 2 * 10^14 on one position.
## Cost
Time O(n + q). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ q ≤ 200000` - `1 ≤ l ≤ r ≤ n` - `-10^9 ≤ v ≤ 10^9`
Input
The first line contains two integers n and q.
Each of the next q lines contains three integers l, r and v.
Output
Print the n final values on one line, separated by spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.