二阶差分——进行一个等差数列的加

一般的差分用于对一段区间进行加减，但如果在该区间内加减的是一段等差数列呢？

对于一段区间 [l,r], 加一段首项为 s, 末项为 e 的等差数列。其公差 d=(s-e)/(r-l+1)

为简化问题讨论，先假设这段区间都为 0。

原数组：0 0 0 0 0 0 0
添加后的数组：0 0 4 6 8 0 0
第一次差分：0 0 4 2 2 -8 0

观察发现，对于第一次差分后的数组 d1[]，d1[l]+=s，d1[i]+=d l<l<=r，d1[r+1]-=((r-l)*d+s)
如果仅仅进行一次差分，似乎还不是很方便。观察数组 d1[]，发现对于 (l,r] 事实上又是一段区间修改。于是再次尝试进行差分。

第二次差分：0 0 4 -2 0 -10 8

观察第二次差分后的数组，尝试推导。

d1[l]=a[l]-a[l-1],a[l]+=s,d1[l]+=s;
d2[l]=d1[l]-d1[l-1],d2[l]+=s;
d2[l+1]=d1[l+1]-d1[l],d2[l+1]+=(d-s)

d1[i]+=d,l<i<=r;
d2[i]=d1[i]-d1[i-1],不变;

d1[r+1]=a[r+1]-a[r],d1[r+1]-=((r-l)*d+s);
d2[r+1]=d1[r+1]-d1[r],d2[r+1]-=s+(r-l+1)*d;
d2[r+2]=d1[r+2]-d1[r+1],d2[r+2]+=(r-l)*d+s;

即

d2[l]+=s;
d2[l+1]+=(d-s);
d2[r+1]-=s+(r-l+1)*d;
d2[r+2]+=s+(r-l)*d;