370. Range Addition - cocoder39/coco39_LC GitHub Wiki

370. Range Addition

initial idea is updating all updated elements, the complexity is O(updates.size() * length). Here a brilliant idea is updating slack only. It is an variant of range sum - immutable.

Instead of updating all elements within the range, we consider the increase between the changed element and its previous element. Say update = [2, 7, 5], then

res[2] - res[2 - 1] = 5;
res[3] - res[3 - 1] = 0;
...
res[7] - res[7 - 1] = 0;
res[8] - res[8 - 1] = -5

time complexity is improved to O(length + updates.size())

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> res(length);
        for (auto update : updates) {
            res[update[0]] += update[2];
            if (update[1] + 1 < length) {
                res[update[1] + 1] -= update[2];
            } 
        }    
        
        for (int i = 1; i < length; i++) {
            res[i] += res[i - 1];
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️