DSA problem
Range Addition
You are given an integer length and an array updates where updates[i] = [startIdx_i, endIdx_i, inc_i].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdx_i], arr[startIdx_i + 1], ..., arr[endIdx_i] by inc_i.
Return arr after applying all the updates.
Applying each update naively costs O(length) per operation. The difference-array trick lets you record each update in O(1) and reconstruct the final array with a single prefix-sum pass.
Examples
Example 1
Input:
length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]Output:
[-2,0,3,5,3]Explanation: Start with [0,0,0,0,0]. After [1,3,2]: [0,2,2,2,0]. After [2,4,3]: [0,2,5,5,3]. After [0,2,-2]: [-2,0,3,5,3].
Example 2
Input:
length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]Output:
[0,-4,2,2,2,4,4,-4,-4,-4]Explanation: Each range update is recorded as a +inc at the start and a -inc just past the end, then a prefix sum yields the result.
Example 3
Input:
length = 1, updates = [[0,0,5]]Output:
[5]Explanation: A single-element array receives an increment of 5 at its only index.
Constraints
- 1 <= length <= 10^5
- 0 <= updates.length <= 10^4
- 0 <= startIdx_i <= endIdx_i < length
- -1000 <= inc_i <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.