等差数列与二阶前缀和

设 \(a\) 是原数组，\(b\) 是一阶差分数组，\(c\) 是二阶差分数组。

首先，公差 \(d=(t-s)/(R-L)\)。

考虑给一个区间 \([L,R]\) 加上首项为 \(s\)，末项为 \(t=s+(R-L)\times d\) 的等差数列对 \(a\) 的影响。

\[ a_x=a_x+s+(x-L)\times d \]

由于 \(b_i=a_i-a_{i-1}\) ，那么：

\[ \begin{align} &\text{} \\ b_L&=(a_L+s)-a_{L-1}\\&=b_L+s \\ &\text{}\\ b_x&=[a_x+(x-L)\times d]-[a_{x-1}+(x-1-L)\times d]\\&=b_x+d\quad(x\in[L+1,R]) \\ &\text{}\\ b_{R+1}&=a_{R+1}-(a_R+t)\\&=b_{R+1}-t \end{align} \]

又 \(c_i=b_i-b_{i-1}\) ：

\[ \begin{align} &\text{} \\ c_L&=(b_L+s)-b_{L-1}\\&=c_L+s \\ &\text{}\\ c_{L+1}&=(b_{L+1}+d)-(b_L+s)\\&=c_{L+1}+d-s \\ &\text{}\\ c_x&=(b_x+d)-(b_{x-1}+d)\\&=c_x\quad(x\in [L+2,R]) \\ &\text{}\\ c_{R+1}&=(b_{R+1}-t)-(b_R+d)\\&=c_{R+1}-d-t \\ &\text{}\\ c_{R+2}&=b_{R+2}-(b_{R+1}-t)\\&=c_{R+2}+t \\ \end{align} \]

所以，相当于改变 \(L,L+1,R+1,R+2\) 四个位置的数值再求两遍前缀和。

注意：差分数组需要开大。