Range Add Update on Array

Given an array of length n initially filled with zeros, apply a list of inclusive range-add updates. Each update adds a value to every element in the selected interval. Return the final array after all updates. This is the simplest setting where lazy propagation ideas are useful.

Input Format

n = size of the array, updates = inclusive range additions

Output Format

final array after all updates

Constraints

  • 1 <= n <= 10^5
  • 1 <= updates.length <= 10^5
  • Each update is [left, right, value] with 0 <= left <= right < n.

Examples

Example 1:

Input:

n = 5
updates = [[1,3,2],[2,4,3]]

Output:

[0,2,5,5,3]

Explanation:

After the first update the array is [0,2,2,2,0]. The second update adds 3 to indices 2 through 4, resulting in [0,2,5,5,3].

Example 2:

Input:

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

Output:

[5,5,2,2]

Explanation:

The first update affects the first two cells and the second update affects the last two cells.

Loading...
Range Add Update on Array - Advanced Trees