Range Addition

Given an integer n and a list of updates, each update is [start, end, delta] (inclusive, 0-indexed). Apply all updates to an array of length n (initially all zeros) and return the final array.

Function signature

func RangeAddition(n int, updates [][]int) []int

Example

n = 5
updates = [[1,3,2],[2,4,3],[0,2,-2]]
output = [-2,0,3,5,3]

Constraints

• 0 <= n <= 200_000
• 0 <= len(updates) <= 200_000
• updates[i] has length 3
• 0 <= start <= end < n
• -1_000_000_000 <= delta <= 1_000_000_000

Notes

• Use a difference array + prefix sum to apply all updates in O(n + m).