差分算法

img
Image

差分其实就是数据之间的差,就是所给的原始数组的相邻元素之间的差值,我们令d[i]=a[i+1]-a[i],一遍for循环即可将差分数组求出来。

其实差分数组是一个辅助数组,从侧面来表示给定某一数组的变化,一般用来对数组进行区间修改的操作

当对一个区间进行增减某个值的时候,他的差分数组对应的区间左端点的值会同步变化,而他的右端点的后一个值则会相反地变化。

  1. [L, R] + v ==> d[L] + v, d[R + 1] -v
  2. 把标记后的差分数组,进行一次前缀和。
  1. d[L] + v <==> [L, n-1] + v

  2. d[R+1] - v <==> [R+1, n-1] - v

  3. d[L] + v ,d[R+1] - v <==>[L, R] + v, [R+1, n-1] - v
  1. d初始可赋0

  2. 然后按照上述公式赋值

  3. 之后用前缀和,将差分数组从前往后依次求和

  4. 再加上原来数组对应的数即可

Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""