日度归档:15 10 月, 2017

差分数组的学习

今天在洛谷八连测R2的群里讨论T2时,遇到了这个问题。搞了半天才弄懂,在这里总结一下,免得以后再要用就忘了。
先出一个问题:
给定一个长度为N的序列A:首先进行X次操作,每次操作在Li和Ri这个区间加上一个数Ci。
进行Y次询问,每次询问Li到Ri的区间和。
有人会说这是树状数组/线段树的裸题,直接用树状数组/线段树去写。但是因为线段树/树状数组不是特别好写(到现在也不会线段树/树状数组好长时间没打忘光了),所以有人就就想出来差分数组这么一个好办法来解决这个问题。
首先,请注意!差分数组的使用是有条件的!我上面所提到的问题因为是离线的,所以可以使用差分数组,而如果是在线的问题,差分数组就不要用了,还是乖乖的去写线段树吧。
大家应该都知道前缀和,而差分数组本质上是前缀和的逆运算,前缀和是加号,而差分数组在推导的时候,则是减号。
对于上面的问题,我们将序列A[n]进行差分,设差分数组D[i]=D[i]-D[i-1]。差分数组推导完毕之后,进行区间加减操作。
假设我们要在闭区间[l,r]上统一加上值k,那么我们只需:令D[l]+=k;D[r+1]-=k即可。然后对D[n]进行前缀和操作,生成数组A[n],再对A[n]进行前缀和操作,生成数组B[n]。那么闭区间[Li,Ri]的区间和就可用B[Ri]-B[Li-1]来表示了。