370. Range Addition

370. Range Addition (Medium)

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:

Input: length = 5, updates = [[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]

Companies:
Google

Related Topics:
Array

Similar Questions:

• Range Addition II (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/range-addition/
// Author: github.com/lzl124631x
// Time: O(N+U)
// Space: O(1)
class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> ans(length, 0);
        for (auto &u : updates) {
            int start = u[0], end = u[1], val = u[2];
            ans[start] += val;
            if (end + 1 < length) ans[end + 1] -= val;
        }
        partial_sum(ans.begin(), ans.end(), ans.begin());
        return ans;
    }
};