学习高阶差分之前，你需要先学习差分

高阶差分简介

记 $\Delta f(x)=f(x+1)−f(x)$。称 $\Delta f(x)$ 为 $f(x)$ 的一阶差分。

同理：记 $\Delta^n f(x)=\Delta^{n−1}f(x+1)−\Delta^{n−1}f(x)$ 。称 $\Delta^nf(x)$ 为 $f(x)$ 的 $n$ 阶差分。

高阶差分公式推导

以二阶差分为例：洛谷：P4231 三步必杀

$N$个柱子排成一排，一开始每个柱子损伤度为$0$。

接下来勇仪会进行$M$次攻击，每次攻击可以用$4$个参数$l$,$r$,$s$,$e$来描述：

表示这次攻击作用范围为第$l$个到第$r$个之间所有的柱子(包含$l$,$r$)，对第一个柱子的伤害为$s$，对最后一个柱子的伤害为$e$。

攻击产生的伤害值是一个等差数列。若$l=1$,$r=5$,$s=2$,$e=10$，则对第$1 \sim 5$个柱子分别产生$2,4,6,8,10$的伤害。

需要的是所有攻击完成之后每个柱子的损伤度。

设$a$表示原数组，$b$表示一阶差分，$c$表示二阶差分。公差$d=\frac{e-s}{r-l}$

根据题意，当我们进行了一次修改，可得：

$$a_i=a_i+s+d(i-l)$$

$a_{i-1}=a_{i-1}+s+d(i-1-l)$

根据差分定义，得到：

$$\begin{aligned}b_i&=a_i-a_{i-1}\\&=b_i+d\end{aligned}$$

$$\begin{aligned}b_{i-1}&=b_{i-1}+d\end{aligned}$$

此时，如果我们把$b_i$看做初始数组，那么我们就可以按照普通的差分做法再做一遍。这就是二阶差分。

再次根据差分定义，得到：
$$\begin{aligned}c_i&=b_i-b_{i-1}\\&=c_l\end{aligned}$$

但是我们要注意端点情况：

$$\begin{aligned}b_l&=a_l+s-a_{l-1}\\&=b_l+s\end{aligned}$$

$$\begin{aligned}b_{r+1}&=a_{r+1}-a_r-e\\&=b_{r+1}-e\end{aligned}$$

$$\begin{aligned}c_l&=b_l+s-b_{l-1}\\&=c_l+s\end{aligned}$$

$$\begin{aligned}c_{l+1}&=b_{l+1}+d-b_l-s\\&=c_{l+1}+d-s\end{aligned}$$

$$\begin{aligned}c_{r+1}&=b_{r+1}-e-b_r-d\\&=c_{r+1}-e-d\end{aligned}$$

$$\begin{aligned}c_{r+2}&=b_{r+2}-b_{r+1}+e\\&=c_{r+2}+e\end{aligned}$$

所以我们每次只需要处理$c_i$数组的五种情况，修改四个点的值即可，统计时求两遍前缀和即可。

代码

这是上面题目的代码，实现起来很简单，$a_i,b1_i,b2_i$分别对应上面的$a_i,b_i,c_i$。

Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
ll a[M],b1[M],b2[M],n,m,l,r,s,e,ans,maxn;
int main(){
    read(n,m);
    while(m--){
        read(l,r,s,e);
        int d=(e-s)/(r-l);
        b2[l]=b2[l]+s;
        b2[l+1]=b2[l+1]+d-s;
        b2[r+1]=b2[r+1]-e-d;
        b2[r+2]=b2[r+2]+e;
    }
    for(int i=1;i<=n;i++){
        b1[i]=b1[i-1]+b2[i];
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b1[i];
        ans^=a[i];
        maxn=Max(maxn,a[i]);
    }
    print(ans,maxn);
    return 0;
}