<div>
You are given an integer length and an array updates where updates[i] = [startIdx<sub>i</sub>, endIdx<sub>i</sub>, inc<sub>i</sub>].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the i<sup>th</sup> operation, you should increment all the elements arr[startIdx<sub>i</sub>], arr[startIdx<sub>i</sub> + 1], ..., arr[endIdx<sub>i</sub>] by inc<sub>i</sub>.
Return arr after applying all the updates.
Example 1:
<pre>Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3] </pre>
Example 2:
<pre>Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]] Output: [0,-4,2,2,2,4,4,-4,-4,-4] </pre>
Constraints:
1 <= length <= 10<sup>5</sup>0 <= updates.length <= 10<sup>4</sup>0 <= startIdx<sub>i</sub> <= endIdx<sub>i</sub> < length-1000 <= inc<sub>i</sub> <= 1000
</div>
题目大意：
统一加一个数到子数组中，如此有好几个操作，求最后数组结果
解题思路：
差分数组，数加到首节点，数减在末节点 + 1，最后累加
解题步骤：
N/A
注意事项：
- 数加到首节点，数减在末节点 + 1，最后累加
- 端点需要累加res[li[0]] += li[2], 而不是res[li[0]] = li[2]
- len(res)而不是len(li)
Python代码：
1
2
3
4
5
6
7
8
9def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
res = [0] * length
for li in updates:
res[li[0]] += li[2] # remember += not =
if li[1] + 1 < len(res): # remember not len(li)
res[li[1] + 1] += -li[2] # remember += not =
for i in range(1, len(res)):
res[i] += res[i - 1]
return res
算法分析：
时间复杂度为O(n + m)，空间复杂度O(1), n, m分别为数组长度和update个数
