Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Given:

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

Output:

[-2, 0, 3, 5, 3]


Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]


Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Na\xc3\xafve Approach [Time Limit Exceeded]

\n

Algorithm

\n

The algorithm is trivial. For each update query, we iterate over the required update range and update each element individually.

\n

C++

\n

Each query of updates is a tuple of 3 integers: (the start and end indexes for the update range) and (the amount by which each array element in this range must be incremented).

\n
vector<int> getModifiedArray(int length, vector<vector<int> > updates)\n{\n    vector<int> result(length, 0);\n\n    for (auto& tuple : updates) {\n        int start = tuple, end = tuple, val = tuple;\n\n        for (int i = start; i <= end; i++) {\n            result[i] += val;\n        }\n    }\n\n    return result;\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : (worst case) where is the number of update queries and is the length of the array. Each of the update operations take up time (worst case, when all updates are over the entire range).

\n
• \n
• \n

Space complexity : . No extra space required.

\n
• \n
\n
\n

#### Approach #2 Range Caching [Accepted]

\n

Intuition

\n
\n
• \n

There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant.

\n
• \n
• \n

Cumulative sums or partial_sum operations apply the effects of past elements to the future elements in the sequence.

\n
• \n
\n

Algorithm

\n

The algorithm makes use of the above intuition to simply store changes at the borders of the update ranges (instead of processing the entire range). Finally a single post processing operation is carried out over the entire output array.

\n

The two steps that are required are as follows:

\n
\n
1. \n

For each update query on the array , we need to do only two operations:

\n
\n
• Update boundary of the range:
• \n
\n

\n\n

\n
\n
• Update just beyond the boundary of the range:
• \n
\n

\n\n

\n
2. \n
3. \n

Final Transformation. The cumulative sum of the entire array is taken (0 - based indexing)

\n

\n\n

\n
4. \n
\n

C++

\n
vector<int> getModifiedArray(int length, vector<vector<int> > updates)\n{\n    vector<int> result(length, 0);\n\n    for (auto& tuple : updates) {\n        int start = tuple, end = tuple, val = tuple;\n\n        result[start] += val;\n        if (end < length - 1)\n            result[end + 1] -= val;\n    }\n\n    // partial_sum applies the following operation (by default) for the parameters {x, x[n], y}:\n    // y = x\n    // y = y + x\n    // y = y + x\n    // ...  ...  ...\n    // y[n] = y[n-1] + x[n]\n\n    partial_sum(result.begin(), result.end(), result.begin());\n\n    return result;\n}\n
\n

Formal Explanation

\n

For each update query on the array , the goal is to achieve the result:

\n

\n\n

\n

Applying the final transformation, ensures two things:

\n
\n
1. It carries over the increment over to every element .
2. \n
3. It carries over the increment (equivalently, a decrement) over to every element .
4. \n
\n

The net result is that:

\n

\n\n

\n

which meets our end goal. It is easy to see that the updates over a range did not carry over beyond it due to the compensating effect of the increment over the increment.

\n

It is good to note that this works for multiple update queries because the particular binary operations here (namely addition and subtraction):

\n
\n
• \n

are closed over the entire domain of Integers. (A counter example is division which is not closed over all Integers).

\n
• \n
• \n

are complementary operations. (As a counter example multiplication and division are not always complimentary due to possible loss of precision when dividing Integers).

\n
• \n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Each of the update operations is done in constant time. The final cumulative sum transformation takes time always.

\n
• \n
• \n

Space complexity : . No extra space required.

\n
• \n
\n
\n

## Further Thoughts

\n

An extension of this problem is to apply such updates on an array where all elements are not the same.

\n

In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of .

\n

@StefanPochmann suggested another method which does not require extra space, but requires an extra linear pass over the entire array. The idea is to apply reverse partial_sum operation on the array (for example, array transforms to ) as an initialization step and then proceed with the second method as usual.

\n
\n

Another general, more complex version of this problem comprises of multiple read and update queries over ranges. Such problems can be solved quite efficiently with Segment Trees by applying a popular trick called Lazy Propogation.

\n

Analysis written by @babhishek21.

\n
'