Loading content...
You are given a positive integer length representing the size of an array, and a list of updates where each update is described by three values: [startIndex, endIndex, increment].
Your task is to simulate applying all the updates to an initially zero-filled array of the given length. For each update operation, you must add the specified increment value to every element in the array from index startIndex to endIndex (both inclusive).
After processing all update operations in the order they are given, return the final state of the array.
Core Challenge: The naive approach of iterating through each range for every update would be inefficient for large inputs. Think about how you can use the properties of cumulative sums to optimize the update process.
Key Insight: Instead of updating every element in the range for each operation, consider marking only the boundaries of change. A difference array technique allows you to record where changes start and stop, then reconstruct the final array with a single pass using prefix sums.
length = 5
updates = [[1,3,2],[2,4,3],[0,2,-2]][-2,0,3,5,3]Starting with array [0,0,0,0,0]: • After [1,3,2]: Add 2 to indices 1-3 → [0,2,2,2,0] • After [2,4,3]: Add 3 to indices 2-4 → [0,2,5,5,3] • After [0,2,-2]: Add -2 to indices 0-2 → [-2,0,3,5,3] The final array is [-2,0,3,5,3].
length = 10
updates = [[2,4,6],[5,6,8],[1,9,-4]][0,-4,2,2,2,4,4,-4,-4,-4]Starting with array [0,0,0,0,0,0,0,0,0,0]: • After [2,4,6]: Add 6 to indices 2-4 → [0,0,6,6,6,0,0,0,0,0] • After [5,6,8]: Add 8 to indices 5-6 → [0,0,6,6,6,8,8,0,0,0] • After [1,9,-4]: Add -4 to indices 1-9 → [0,-4,2,2,2,4,4,-4,-4,-4]
length = 5
updates = [[1,3,5]][0,5,5,5,0]Starting with array [0,0,0,0,0]: • After [1,3,5]: Add 5 to indices 1-3 → [0,5,5,5,0] Only one update operation is applied.
Constraints