Batch Range Additions

01 · Question

Given an integer array and updates (left,right,delta), add delta to every index in the half-open interval [left,right). Return the final array without modifying the input. All updates satisfy 0 <= left <= right <= n; empty ranges are allowed. Values and accumulated sums fit signed 64-bit integers.

Example: nums=[1,2,3], updates=[(0,2,4),(1,3,-1)] returns [5,5,2].

02 · Analysis

Record +delta at left and -delta at right in an n+1 difference array. A prefix scan carries each contribution through exactly its intended interval; the extra slot handles right=n. Add the running increment to each original value. Empty updates cancel at the same index. With q updates, time O(n+q), auxiliary space O(n), output space O(n). This batching requires no intermediate queries.

03 · Solution

Reference solution

1def apply_range_additions(nums, updates):
2    diff = [0] * (len(nums) + 1)
3    for left, right, delta in updates:
4        diff[left] += delta
5        diff[right] -= delta
6    result = []
7    running = 0
8    for i, value in enumerate(nums):
9        running += diff[i]
10        result.append(value + running)
11    return result

Find Pivot Index