Summary -「Generalised Difference」

cirnovsky /

区间加法可以差分的原因是 Δi=Δi1\Delta_i = \Delta_{i-1},所以令 di=ΔiΔi1\textit{d}_i = \Delta_i-\Delta_{i-1},对于一个一般点的 Δi=f({Δ1,,Δi1})\Delta_i = f(\{\Delta_1, \dots, \Delta_{i-1}\}),我们可以令 di=Δif({Δ1,,Δi1})\textit{d}_i = \Delta_i-f(\{\Delta_1, \dots, \Delta_{i-1}\})

这得出了广义一点的差分。那么前缀和的方式即 didi+f({d,,di1})\textit{d}_i \gets d_i+f(\{d, \dots, d_{i-1}\})(其实这里的 ff 改为下标的函数可能更准确一点)。

举个例子,对区间 [l,r][l, r] 中的 i[l,r]i \in [l, r] 操作 aiai+fil+1a_i \gets a_i+f_{i-l+1},其中 ff 是 Fibonacci 数列,也就是说 fi=fi1+fi2f_i = f_{i-1}+f_{i-2},差分数组即 di=aiai1ai2d_i = a_i-a_{i-1}-a_{i-2},操作即 dldl+1d_l \gets d_l+1dr+1dr+1+frl+2d_{r+1} \gets d_{r+1}+f_{r-l+2}dr+2dr+2+frl+1d_{r+2} \gets d_{r+2}+f_{r-l+1},前缀和方法即 didi+di1+di2d_i \gets d_i+d_{i-1}+d_{i-2}

差分是导函数的一个演绎,即令研究范围中的 ϵ=1\epsilon = 1 而得来的(在实数中令 ϵ=lim1x+x\epsilon = \lim\limits_{\frac{1}{x} \rightarrow +\infty}x 做差分即可得到导函数)。