差分
差分实质上就是前缀和的逆运算,主要解决连续多次在部分区间增加某个值 c
之后,求更新之后的数组。
问题:
输入一个长度为n的整数序列。接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2
问题求解
该题最直观的思想是针对每次操作遍历一次数组,然后在相应的位置增加 c ,该方法的时间复杂度为 $O(mn)$ 。现在我们采用差分的方法来进行算法的优化。
对于一个数组 b[n+1]
:
([x, x, x, l, x, x, r, r+1, x, n])
如果在 b[l]
位置加上 c
,则从 b[l]
开始的所有前缀和数组都会加上 c
;同理,为了保证只在 [l,r]
的区间增加 c
,我们需要将 b[r+1]-=c
。最终我们只需要根据得到的数组 b
求前缀和即可。采样该方法对于每次的区间操作只需要 O(1)
的时间复杂度,而构造差分矩阵的时间复杂度为 O(n)
,因此总共的时间复杂度为 O(n)
。
核心代码:
def insert(b, l, r, c):
b[l] += c
b[r+1] -= c
if __name__ == "__main__":
n, m = map(int, input().split())
a = [0] * (n + 10) # 原值数组
b = [0] * (n + 10) # 差分数组
nums = list(map(int, input().split()))
for index, val in enumerate(nums):
a[index+1] = val
for i in range(1, n+1): # 强烈建议都从 1 开始
insert(b, i, i, a[i])
while m > 0:
m -= 1
l, r, c = map(int, input().split())
insert(b, l, r, c)
for i in range(1, n+1):
b[i] += b[i-1]
for i in range(1, n+1):
print(b[i], end=" ")
应该可以在倒数第二个循环的时候直接print了,不用再循环一遍啦~
感激!!!
棒!
竟然得到了大佬的认可!!!
我好菜的.