370. Range Addition

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]

// Brute Force
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) { // time: O(k * n); space: O(n)
    vector<int> res(length, 0);
    for (auto& update : updates) {
        int startIdx = update[0], endIdx = update[1], delta = update[2];
        for (int i = startIdx; i <= endIdx; ++i) {
            res[i] += delta;
        }
    }
    return res;
}

這個O(n + k)的方法有點類似discrete-time signal processing，對每個update的操作來說，在startIdx的數加上操作的值，因為到endIdx都是需要加上那個操作的值，所以我們只需要在endIdx之後把那個操作的值減掉就行。如果endIdx已經是最後一個index那就不需要減掉的操作。最後把res array掃過一遍，把當下的和算出來就是當前index的數。

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) { // time: O(k + n); space: O(n)
    vector<int> res(length, 0);
    for (auto& update : updates) {
        int startIdx = update[0], endIdx = update[1], delta = update[2];
        res[startIdx] += delta;
        if (endIdx < length - 1)
            res[endIdx + 1] -= delta;
    }
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        sum += res[i];
        res[i] = sum;
    }
    return res;
}