差分

· · 科技·工程

六年级蒟蒻，不喜易喷

（你听说了吗？昨天有个小兄弟给我点赞，回家的路上捡到了100AC币）

luogu

1.概念

在讲差分之前，先来讲讲你们熟悉的前缀和

\text{a的前缀和数组b}： b_1=a_1 b_2=b_1+a_2 b_3=b_2+a_3 \cdot\cdot\cdot

差分就是前缀和的逆运算，用O(1)的时间操作,用O(n)的时间做处理

\text{a的差分数组b}： b_1=a_1 b_2=a_2-a_1 b_3=a_3-a_2 \cdot\cdot\cdot

差分数组的模板给到大家

cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    b[i]=a[i]-a[i-1];
}

2.差分的作用

所以这个差分有啥用呢？能吃吗？

先来看一道题：

给出数组a，有m条操作，每次给出l,r,c三个数,意为将a数组里第l个数到第r个数全部增加c，问m次操作之后，a数组的各个数是多少？

m<=100 n<=100 1<=l<=r<=n 1<=a[i],c<=10000

我赌五毛钱，你第一眼看到这道题的第一反应是暴力

但如果是数据范围改了亿下呢？ m<=1e6 n<=1e6 1<=l<=r<=n 1<=a[i],c<=1e6

这时，差分的好处就出来了，上面我们也讲到了差分的时间复杂度：

差分就是前缀和的逆运算，用O(1)的时间操作,用O(n)的时间做处理

那么我们就可以用O(m)的时间操作完m次操作，最后用O(n)的时间做一下处理，时间复杂度O(n+m)

但，要怎么在O(m)的时间里操作完m次操作呢？

咳咳，我们先把b数组看作一条长长的线，在b[l]增加c，在b[r+1]减少c

（路人甲：我好歹也是个Oler，你别蒙我，这有什么用！）

我不是说过了嘛

差分就是前缀和的逆运算

先假设b数组全是0,a数组也全是0 b:0 0 0 0 0

现在要让第1个数到第4个数增加1，就在b[1]增加1，在b[r+1]减少1 b:1 0 0 0 -1

求一遍前缀和 b:1 1 1 1 0

这不就行了吗？

这就是差分的用处：将区间内的所有数加上某一个数

差分的板子也给到大家

for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++)
        b[i]+=b[i-1];

3.二维差分

前面讲了一维差分，那现在来讲讲二维差分吧

先上例题：

有一个n*n的二维矩阵a，现在给出m个操作，每次给出x1,y1,x2,y2,c五个数，代表将左上角坐标为(x1,y1)，右下角坐标为
(x2,y2)的一个矩阵内的数增加c，请输出操作完成后的二维矩阵

举个例子：
1 2 3 4
1 2 5 3
2 7 4 2
6 9 4 8

操作：1 2 2 3 1

那么矩阵要增加的部分如下：
# . . #
# . . #
# # # #
# # # #

那么操作完成的矩阵为：
1 3 4 4
1 3 6 3
2 7 4 2
6 9 4 8
\text{数据范围：} n<=10^3\kern{10pt} m<=10^6\kern{10pt} 1<=x1,y1,x2,y2<=n \kern{10pt}1<=a[i],c<=10^6

其实，二维差分的方式与一维是有联系的，也是用前缀和来还原数组。

进入正题：

先上一张图： 先将(x1,y1)增加c，则黄色部分全部增加c 但这肯定不是我们想要的结果，我们先将(x1,y2+1)减去c，则绿色部分减少c 当然，还要将(x2+1,y1)减去c，让红色部分减少c 你觉得大功告成了吗？没有！别做梦了！ 蓝色部分是我们减去了两次的，所以我们还要给(x2+1,y2+1)增加c

然后与一维差分一样，前缀和还原数组。

二维差分就是这个样子

void cf(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
    return ;
}

4.例题

这里推荐一些差分的模板题，并给出相应题解

acwing.736 安迪种树

acwing.736 安迪种树 题解

luogu.P2367 语文成绩

luogu.P2367 语文成绩 题解