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.
- Thinking of using advanced data structures? You are thinking it too complicated.
- For each update operation, do you really need to update all elements between i and j?
- Update only the first and end element is sufficient.
The optimal time complexity is O(k + n) and uses O(1) extra space.
譬如数组nums[n], 修改(i, j, a). 只修改nums[i] = a, nums[j + 1] = -a，就可以了。前缀和数组就是所求结果。