Solution
from typing import List
from itertools import accumulate
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
d = [0] * length
for l, r, c in updates:
d[l] += c
if r + 1 < length:
d[r + 1] -= c
return list(accumulate(d))
# 本地测试
if __name__ == "__main__":
sol = Solution()
print(sol.getModifiedArray(5, [[1,3,2],[2,4,3],[0,2,-2]])) # [-2,0,3,5,3]
Solution 2
from typing import List
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
tree = BinaryIndexedTree(length)
for l, r, c in updates:
tree.update(l + 1, c)
tree.update(r + 2, -c)
return [tree.query(i + 1) for i in range(length)]
# 本地测试
if __name__ == "__main__":
sol = Solution()
print(sol.getModifiedArray(5, [[1,3,2],[2,4,3],[0,2,-2]])) # [-2,0,3,5,3]