Summary -「Generalised Difference」
区间加法可以差分的原因是 Δi=Δi−1,所以令 di=Δi−Δi−1,对于一个一般点的 Δi=f({Δ1,…,Δi−1}),我们可以令 di=Δi−f({Δ1,…,Δi−1})。
这得出了广义一点的差分。那么前缀和的方式即 di←di+f({d,…,di−1})(其实这里的 f 改为下标的函数可能更准确一点)。
举个例子,对区间 [l,r] 中的 i∈[l,r] 操作 ai←ai+fi−l+1,其中 f 是 Fibonacci 数列,也就是说 fi=fi−1+fi−2,差分数组即 di=ai−ai−1−ai−2,操作即 dl←dl+1,dr+1←dr+1+fr−l+2,dr+2←dr+2+fr−l+1,前缀和方法即 di←di+di−1+di−2。
差分是导函数的一个演绎,即令研究范围中的 ϵ=1 而得来的(在实数中令 ϵ=x1→+∞limx 做差分即可得到导函数)。