定义：

a数组是diff数组的前缀和，换句话说就是diff数组是a数组的差分数组。所以前缀和与差分是 共轭逆推 关系，所以可以推导出：diff[i]=a[i]-a[i-1]

应用

经典例题：

P2367 语文成绩

n<=$5×10^6$,暴力行不通，就可以用差分

把每个区间都用a[l]+=t,a[r+1]-=t，处理，再跑前缀和加上原本的分数取最小值就行了

P7404 [JOI 2021 Final] 有趣的家庭菜园4

允许选一个区间全部加1，对于a数组来说，选2个点，使得a[l]++,a[r]--

先把a数组全部求出来，然后两个指针，前面的数找到小于等于 0的数时就停下，后面的数栈到大于等于0的数时就停下，然后开始对调。其中一个满足了就继续移动。

二次差分

P4231 三步必杀

公差(c)：$(e-s) / (r-l)$，项数(x)：$r-l+1$，把公式先列出来

然后在 $s_l$ 到 $s_r$ 中间插入一个上面的等差数列

那么 $a_l$ += $c$ , $a_{l+1}$ += $c$ , .... $a_r$ += $c$ , $a_{r+1}$ -= $c*x$

换到diff数组里就是 $diff_l$ += $c$ ，$diff_{r+1}$ -= $c$ ，同理，$diff_{r+1}$ -= $c*x$，$diff_{r+2}$ = $c*x$

然后每一次输入的时候放进去就可以了。

但是没考虑到首项和公差不相等

所以应该是这样：a[l]+=s , a[r+1]-=s, a[l+1]+=c, ...... a[r]+=c, a[r+1] -= c*(x-1)

换成diff数组就是diff[l] += s, diff[l+1]-=s, diff[r+1]-=s, diff[r+2]+=s, diff[l+1]+=c,

diff[r+1]-=c, diff[r+1]-=c*(x-1), diff[r+2]+=c*(x-1)