Many Range Updates

A list of length zeros receives a series of updates. Each update is [start, end, amount] and adds amount to every position from start to end, both included. Write apply_updates(length, updates) that returns the list after all the updates.

The list and the number of updates can both be large, so adding to every position of every update one at a time can get slow.

Examples

apply_updates(5, [[1, 3, 2], [2, 4, 3], [0, 2, -2]])
# returns [-2, 0, 3, 5, 3]

apply_updates(3, [])
# returns [0, 0, 0]

apply_updates(4, [[0, 3, 1]])
# returns [1, 1, 1, 1]

In the first example the list goes from [0, 0, 0, 0, 0] to [0, 2, 2, 2, 0], then [0, 2, 5, 5, 3], then [-2, 0, 3, 5, 3].

Constraints

• 0 <= length <= 100,000
• 0 <= len(updates) <= 100,000
• 0 <= start <= end < length
• -1,000 <= amount <= 1,000