数组差分与前缀和

GalaxyOier · 2021-10-03 10:49:34 · 个人记录

数组差分与前缀和

一、差分

差分就是把数组表现成初始数和一堆差的形式。
例：7 9 2 1 4 5
差分形式：7 2 -7 -1 3 1
这时可以发现:

当把数组转换成差分形式后，就可以很轻松的进行区间修改
如果想要把a[x]-a[y]同时加上delta，只需将d[x]+Δ,d[y+1]-Δ，这时再

就可以得出修改后的a[n]了。
差分的优点在于可以通过修改差分数组起始和结尾来迅速进行区间修改。

二、前缀和

前缀和本身与差分差不多。
例：7 9 2 1 4 5
前缀和形式：7 16 18 19 23 28
通过观察，可以发现a[i]=d[i+1]-d[i]
那么d[x]-d[y-1]就可以求出[a[x],a[y]]这个区间的和，从而实现区间求和的目的。
前缀和的优点在于可以通过将数组两项做差方便的进行区间求和。