370. Range Addition

I implemented in a naive way. But it got TLE.

1:  class Solution {  
2:  public:  
3:    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {  
4:      vector<int> res(length, 0);  
5:      for (int i = 0; i < updates.size(); i++) {  
6:        for (int j = updates[i][0]; j <= updates[i][1]; j++) {  
7:          res[j] += updates[i][2];  
8:        }  
9:      }  
10:      return res;  
11:    }  
12:  };  

The hits provides a O(n+k) running time solution. Let's see the example. Given length = 5.
update(1,3,2), we should have [0, 2, 2, 2, 0]. What if we only record two positions? It means we need to do sum from the left to right to get the new array. So we can modify the array to be [0, 2, 0, 0, -2] and when we do sum from left to right, i.e. res[i] = res[i] + res[i-1], we'll get [0, 2, 2, 2, 0] which is exactly the same as our expected array. So for each update(i, j, a), we add a to res[i] and subtract a from res[j+1]. In the end, we sum up the res from left to right following res[i] = res[i] + res[i-1].

1:  class Solution {  
2:  public:  
3:    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {  
4:      vector<int> res(length+1, 0);  
5:      for (int i = 0; i < updates.size(); i++) {  
6:        res[updates[i][0]] += updates[i][2];  
7:        res[updates[i][1]+1] -= updates[i][2];  
8:      }  
9:      for (int i = 1; i < length; i++) {  
10:        res[i] = res[i]+res[i-1];  
11:      }  
12:      res.pop_back();  
13:      return res;  
14:    }  
15:  };