浅谈差分

1.前言

同步于 cnblogs 发布。

前置芝士：

• 基本树上操作，lca。（用于树上差分。）

如有错误，欢迎各位大佬指出。（顺便复习一下远古算法。）

2.什么是差分

我们先给定一个数组 a，长度为 n，我们可以构造一个差分数组 b，使得对于任意的 i(1\le i \le n)，\displaystyle\sum_{j = 1}^{i} b_j=a_i。

那么如何构建一个普通的差分数组呢？

不难想到，我们假定 a_0=0，则此时，对于任意的 b_i，我们令它等于 a_i-a_{i-1}，则当我们算 \displaystyle\sum_{j=1}^{i}b_j 时，所有 a_1,a_2...a_{i-1} 都会抵消掉，只剩下 a_i，也正好满足了我们的前提条件。

3.差分数组的最普通应用

首先，我们先引入一个例题 P2367 语文成绩。题目意思大概就是说先给你一个序列，然后在进行区间加，最后求得区间的最小值即可。

而对于这种区间加减的操作，正是差分能够大展拳脚的地方。

我们先维护一个差分数组 b（以后皆假设差分数组为 b。），先将它全部初始化为0。假设当前我们面临的操作是将 [l,r] 这个区间全部加上 x。由于差分的前缀和便是原数组，所以我们可以一开始将 b_l+x，但是当你在算前缀和的时候，对于 r+1 及以后的前缀和，他都会多算一个 +x，所以，为了将其抵消掉，我们需要将 b_{r+1}-x。

最后，处理完这些询问之后，我们在最后求一次前缀和即可。

可以发现，差分修改操作时间复杂度为 O(1)，查询时间复杂度为 O(n)。

最后贴上一份代码:

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[5000005],c[5000005];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    while(q--)
    {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        c[l]+=x,c[r+1]-=x;//由于是差分，将c[l]+x，但为了抵消掉它对后面的贡献，我们将 c[r+1]-x 
    }
    int minn=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        c[i]+=c[i-1];//求前缀和 
        a[i]+=c[i];//原数组记得加上 
        minn=min(minn,a[i]);//最小值 
    }
    cout<<minn<<endl;
}

4.差分数组的二维形式

我们上述的，全都是一个序列（一维）的情况，但是，差分仍然可以扩展到二维。（对于其定义，与一维相类似，这里不做过多赘述）

假设我们当前修改的二维区间为 (x1,y1) 到 (x2,y2)，加上 x（x1\le x2,y1\le y2）。显然，我们一开始仍然需要将起始位置 b_{x1,y1}+x。但随即我们可以发现，对于所有 x1-n,y1-n 它的值都被加上了 x，但这个区间实际只能管到 (x2,y2)，所以，对于 (x1,y2+1) 以及 (x2+1,y1) 以后的所有格子都是当前加不到的，所以我们又将 b_{x1,y2+1}-x,b_{x2+1,y1}-x。但随即我们又可以发现，虽然减是减了，但对于 (x2+1,y2+1) 及以后的值，在差分算前缀和时被减了两次，所以我们需要将 b_{x1+1,y2+1}+x。

下面配上一个图方便理解。（图略丑，勿喷。）

假设我们要区间加 (2,2)-(4,4)，其中黄色表示被 c_{x1,x2} 影响到的范围，蓝色表示 c_{x1,x2} 加后多影响到的地方，及 b_{x1,y2+1}-x,b_{x2+1,y1}-x 影响到的地方，绿色表示被黄色蓝色一起影响，最终被多减了一次，需要加 x 的区域。

大概就是:

void chafen(int x1,int y1,int x2,int y2,int x)
{
    b[x1][y1]+=x;
    b[x1][y2+1]-=x;
    b[x2+1][y1]-=x;
    b[x1+1][y2+1]+=x;
}

最后还是给一个比较简单的例题吧。P3717 [AHOI2017初中组]cover，虽然可以不用二维差分做，但当一个练习的板子题还是挺好的。

5.树上差分

这是一种非常常考也非常实用的一种差分形式。

我们先给出一种最基本的树上差分形式。即我们现在要完成的是将 x-y 的路径上的所有节点 +x。

然后我们给出树上差分的定义，即我们假设第 i 个点的点权为 a_i，然后我们维护差分数组 b 表示对于任意节点 i，使得 i 的所有子节点的 b 之和（包括他本身）为 a_i。

然后，我们来处理树上差分。首先，我们可以把 x-y 的路径看做 x-lca(x,y)-y 的路径。（lca 的求法这里不做赘述。）然后，由于我们要将这一段的路径全部加 z。我们可以发现，当我们对 b_x,b_y 分别加上 z，就可以满足将 x- 根节点的路径以及 y- 根节点的路径全部 +z，但我们发现，不仅 fa_{lca(x,y)}- 根节点的路径多加了两遍 x，而且 lca 这个节点被加了两次，但他只能被加一次，所以它也多加了一次。为了将这些效果抵消，我们可以在 b_{lca(x,y)}-z，则对于 lca(x,y)- 根节点的路径，我们都被抵消了一次 z。但是，在抵消之后，fa_{lca(x,y}- 根节点的路径我们仍然多加了一次 z，所以此时，我们需要将 b_{fa_{lca(x,y)}}-z，便可以完美抵消掉了！

核心代码:

void tree(int x,int y,int z)
{
    b[x]+=z,b[y]+=z;
    b[lca(x,y)]-=z;b[fa[lca(x,y)]]-=z;
}

最后再奉上一个比较好想的例题：P6869 [COCI2019-2020#5] Putovanje

6.后记

虽然在维护序列时，我们完全可以用线段树树状数组等一列数据结构来代替差分这种查询较慢的结构，但差分终究还是一个好写好想的算法，是不容易出错的。毕竟，如果考场上你在面临树上路径的操作时，不会树上差分，打一个码量极大还容易错的的树链剖分就太吃亏了。