差分进阶：累加等差数列类问题的求解
引言：
差分是信息学奥赛中的一个基础算法，但是其往往以难题的形式出现在竞赛的后两题中。本文将介绍差分的一种进阶应用：二次差分。这种方法主要应用在区间修改时累加等差数列的情况。
复习回顾：差分的基本概念
差分是前缀和的逆运算。顾名思义，差分是作差，前缀和是作和。具体而言，对于原数组a与差分数组d差分的基本公式如下：
d[i]=a[i]-a[i-1]
差分的主要用途是区间修改+单点查询。通过差分可以只用修改两个点的值就能对整个区间进行修改。对于区间[l,r]，利用差分为其加上k的公式如下：
d[l]+=k;d[r+1]-=k
通过以上公式，我们可以在O(1)的时间内进行区间修改。若要还原数组，只需对差分数组做一次前缀和即可。
注意：差分仅适用于加减法的修改，无法进行乘除法修改。
进入正题：二次差分与等差数列问题
问题描述：现有一个数组a，需要在[l,r]的区间内将a的每一项增加一个值，所有增加量可以形成以x为首项，y为末项，d为公差的等差数列
这是典型的区间修改问题，大部分人都会想用差分实现，但此类问题与普通的差分问题有较大差异。我们可以就a数组的状态进行推导：(此处我们设等差数列的项数为4，过程如下表)
| 下标: | l | l+1 | l+2 | l+3(r) | r+1 | r+2 |
|---|---|---|---|---|---|---|
| a数组: | x | x+d | x+2d | x+3d(y) | 0 | 0 |
| 为了能降低以上操作的复杂度，我们对a数组进行差分得到b数组： | 下标: | l | l+1 | l+2 | l+3(r) | r+1 | r+2 |
|---|---|---|---|---|---|---|---|
| b数组 | x | d | d | d(y-2d) | -x-3d(-y) | 0 |
| 虽然我们进行了差分，但是未能达到降低复杂度的目的(差分后复杂度没有变化,仍为O(n),而我们的目标是O(1)实现修改)。观察b数组，我们发现，b[l+1],b[l+2]与b[l+3]的d可以相互抵消，于是我们对b数组进行差分，得到c数组： | 下标： | l | l+1 | l+2 | l+3(r) | r+1 | r+2 |
|---|---|---|---|---|---|---|---|
| c数组： | x | d-x | 0 | 0 | -y-d | y |
至此，我们已将a，b数组需要修改整个区间的方法转化为c数组只需要修改4个点的方法，复杂度降为O(1)
由此，我们得出：对于将区间[l,r]增加特定值，使所有增加量形成首项为x，末项为y，公差为d的等差数列，有以下公式：
c[l]+=x;c[l+1]+=(d-x);c[r+1]-=(y+d);c[r+2]+=y
其中，c为差分数组。这一操作因为做了两次差分，所以称为二次差分(又名二阶差分)
注意：由于我们进行了两次差分操作，在还原数组时需要进行两次前缀和
初步运用：P4231 三步必杀
根据题意，每一次攻击对于区间[l,r]范围内的柱子造成的伤害值为以s为首项，e为末项，d=(e-s)/(r-l)为公差的等差数列。因此，我们可以利用上文的结论，通过差分来解决本题。
代码如下：
#include<bits/stdc++.h>
#define int long long //记得开long long
using namespace std;
const int N=1e7+100;
int c[N],n,m,l,r,s,e;
int ans=0;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);//关闭同步流,提速
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>l>>r>>s>>e;
int d=(e-s)/(r-l);//计算公差
c[l]+=s;c[l+1]+=(d-s);c[r+1]-=(e+d);c[r+2]+=e;//套用上文的结论
}
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
}
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
ans=max(ans,c[i]);//求最大值
}//记得还原数组时需要做两次前缀和
for(int i=1;i<=n;i++){
c[i]=c[i-1]^c[i];//求异或和
}
cout<<c[n]<<" "<<ans;
return 0;
}本题是对上文结论的基础运用，下面来看一道更难的题。
进阶运用：P5026 Lycanthropy
由题意可知，本题中也包含涉及修改为等差数列的操作，只不过操作的区间很多，具体情况如下：(时间关系，利用一下题解中的图)
我们可以尝试简化一下差分公式，以避免写程序时出现不必要的错误。
在区间[i-3v+1,i-2v]中进行操作:
| i-3v+1 | i-3v+2 | i-2v+1 | i-2v+2 |
|---|---|---|---|
| 1 | 0 | -v-1 | v |
在区间[i-2v+1,i-v-1]中进行操作：
| i-2v+1 | i-2v+2 | i-v | i-v+1 |
|---|---|---|---|
| v-1 | -v | 0 | 1 |
| 在区间[i-v+1,i]中进行操作: | i-v+1 | i-v+2 | i+1 | i+2 |
|---|---|---|---|---|
| -1 | 0 | v+1 | -v |
在区间[i+1,i+v-1]中进行操作:
| i+1 | i+2 | i+v | i+v+1 |
|---|---|---|---|
| -v+1 | v | 0 | -1 |
在区间[i+v+1,i+2v]中进行操作:
| i+v+1 | i+v+2 | i+2v+1 | i+2v+2 |
|---|---|---|---|
| 1 | 0 | -v-1 | v |
在区间[i+2v+1,i+3v-1]中进行操作：
| i+2v+1 | i+2v+2 | i+3v | i+3v+1 |
|---|---|---|---|
| v-1 | -v | 0 | 1 |
通过列举所有情况我们发现，许多的操作互相抵消，只剩下如下的操作：
c[i - 3 * v + 1] ++;
c[i - 2 * v + 1] -= 2;
c[i + 1] += 2;
c[i + 2 * v + 1] -= 2;
c[i + 3 * v + 1] ++;然而，因为下标涉及减法，可能越界，所以我们需要将每一个下标加上一个大数，数组相应要多开4倍(注意是4倍，否则85分),最后做两次前缀和然后输出答案。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int c[4*N],v,x,n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v>>x;
c[x-3*v+1+N]++;//操作
c[x-2*v+1+N]-=2;
c[x+1+N]+=2;
c[x+2*v+1+N]-=2;
c[x+3*v+1+N]++;
}
for(int i=1;i<=N*2;i++){
c[i]=c[i-1]+c[i];
}
for(int i=1;i<=N*2;i++){
c[i]=c[i-1]+c[i];//两次前缀和
}
for(int i=N+1;i<=N+m;i++){
cout<<c[i]<<" ";//输出，注意从N+1开始到N+m结束
}
return 0;
}本题的难度较上题有较大提升，不仅在于操作更加复杂，还在于需要考虑数组越界问题。
结语：
二次差分问题是差分内容中较难的一个分支，然而它在求解修改等差数列类问题中效率较高，进而得到广泛应用。理解并掌握这一内容，需要进行细致的推理，以完全掌握此类规律。