Range Addition

Problem Statement

In this problem, you are provided with an integer length indicating the size of an array arr which is initially filled with zeros. An array updates is also given, wherein each element is a tuple of the form [startIdxi, endIdxi, inci]. These tuples specify a range in the arr (from startIdxi to endIdxi inclusive) where each element in this range should be incremented by inci.

The task is to apply these increments to the arr according to the specified ranges in updates and return the modified arr after all updates have been applied.

Examples

Example 1

Input:

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

Output:

[-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]

Constraints

• 1 <= length <= 105
• 0 <= updates.length <= 104
• 0 <= startIdxi <= endIdxi < length
• -1000 <= inci <= 1000

Approach and Intuition

To solve this problem optimally, we can employ the concept of a difference array along with prefix sums. Here's how this can be approached:

1. Initialize a list arr of length length+1 to zero. This extra space is used to prevent index out of bounds and simplify calculations.

2. For each update [startIdxi, endIdxi, inci]:

   • Increment arr[startIdxi] by inci. This is because arr[startIdxi] and all elements after it should be increased by inci.
   • Decrement arr[endIdxi + 1] by inci (if within bounds). This will mark the end of increment operation beyond the endIdxi position.

3. Compute the prefix sums of the arr to translate these increment and decrement operations into actual values for each position in the original array arr[0:length-1].

4. The resulting array after applying prefix sums will represent the expected outcome after all update operations are applied onto the initial array filled with zeros.

Using this differential approach converts the otherwise O(n*m) complexity (where n is the length of the array and m the number of updates) to a more efficient O(n + m) complexity, due to linear traversals for applying updates and computing prefix sums separately.

Solutions

vector<int> updateArray(int size, vector<vector<int> > modifications)
{
    vector<int> modifiedArray(size, 0);
    
    for (auto& update : modifications) {
        int startIndex = update[0], endIndex = update[1], increment = update[2];
    
        modifiedArray[startIndex] += increment;
        if (endIndex < size - 1)
            modifiedArray[endIndex + 1] -= increment;
    }
    
    partial_sum(modifiedArray.begin(), modifiedArray.end(), modifiedArray.begin());
    
    return modifiedArray;
}