六年级蒟蒻,不喜易喷
(你听说了吗?昨天有个小兄弟给我点赞,回家的路上捡到了100AC币)
1.概念
在讲差分之前,先来讲讲你们熟悉的前缀和
a的前缀和数组b:
b1=a1
b2=b1+a2
b3=b2+a3
⋅⋅⋅
差分就是前缀和的逆运算,用O(1)的时间操作,用O(n)的时间做处理
a的差分数组b:
b1=a1
b2=a2−a1
b3=a3−a2
⋅⋅⋅
差分数组的模板给到大家
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
数据范围:n<=103m<=1061<=x1,y1,x2,y2<=n1<=a[i],c<=106
其实,二维差分的方式与一维是有联系的,也是用前缀和来还原数组。
进入正题:
先上一张图:
先将(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.例题
这里推荐一些差分的模板题,并给出相应题解
牛逼大佬
六年级大佬 我跪了
(爬行痕迹)____stO