顾z
2018-09-20 08:18:47
百度百科中的差分定义 //其实这完全和要讲的没关系 qwq
进去看了之后是不是觉得看不懂?
那我简单概括一下qwq
差分数组de定义:记录当前位置的数与上一位置的数的差值.
栗子
容易发现的是,
看到前面的
那你认为这是前缀和? 的确是qwq.
实际上这并不是真正意义上的前缀和.
前缀和的思想是 根据元素与元素之间的并集关系(和的关系),求出某些元素的和的值.对应的为
而差分的思想与此不同.
差分的思想是 根据元素与元素之间的逻辑关系(大小关系),求出某一位置元素的值.对应的为
What?不懂?看下面
继续捡起刚刚的栗子.
有没有发现不同之处 ( • ̀ω•́ )✧
先看一道题,
有n个数。
m次操作,每一次操作,给定l,r,del.将l~r区间的所有数增加del;
最后有q个询问,给你 l,r ,每一次询问求出l~r的区间和。
PS: 先进行m个修改操作,后进行查询操作.
如果你是一个巨佬,你会"woc,线段树裸题!" "woc,树状数组裸题!"
然而,今天我要BB的不是这些东西.
是差分数组的运用!
有没有想法? 没有的话那就我来有也是我来
考虑我们差分数组记录的是什么,它记录的是当前位置的数与上一个数的差值.
如果我们在差分数组的
什么?不相信? 那我们来个栗子(要糖炒的
还是刚开始的栗子.
这样是不是达到了区间修改操作,是不是! "是!,tql!!"
这样我们就能做到
我们再定义两个数组(先不要忘记我们的差分数组为
$sum_i$代表$\sum_{j=1}^{i} s_j$ 即代表前缀和. qwq
容易发现的是
什么不理解为什么是
那我们把式子展开看 qwq
两个式子相减的话,我们得到的就是
而我们如果减去
emmmm 差点跑去讲前缀和
所以说我们可以在修改操作完成之后,
具体这个题的代码是这样的↓
#include<bits/stdc++.h>
using namespace std;
int n,m,q,last,sum[10086],b[10086],s[10086];
int main()
{
cin>>n;//n个数
for(int i=1,x;i<=n;i++)
{
cin>>x;//这里实际上不需要a数组,视题而异
b[i]=x-last;//得到差分数组
last=x;//别忘了变化last变量
}
cin>>m;//m次操作
for(int i=1,l,r,del;i<=m;i++)
{
cin>>l>>r>>del;//在[l,r] 加上del
b[l]+=del,b[r+1]-=del;
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+b[i];//这里是处理我们的s数组
sum[i]=sum[i-1]+s[i];//处理我们的sum数组.
}
cin>>q;//q个询问
for(int i=1,l,r;i<=q;i++)
{
cin>>l>>r; //询问[l,r]的区间和.
cout<<sum[r]-sum[l-1]<<endl; //输出即可.
}
}
刚刚涉及到的用途有
你以为差分只有这么多用处吗?
利用差分数组还能算出前缀和,看式子变形!
所以说,上面的代码完全可以改一下,相信大家写出来应该会很容易. (其实是我懒 qwq
差分还有其他用途这里并没有涉及到,所以还需要大家自己去发现去学习 ┓( ´∀` )┏
来一个 差分+二分 结合运用的题目 -->p1083 借教室
看完题目了没? 有没有思路?
想一下,
在 一个订单的起始天+要借的教室数量, 并在该订单结束的那一天的下一天减去要借的教室数量
这样我们再维护一下前缀和,这就样就能知道这些天中,我们借了多少教室! 是不是很巧妙qwq
然后我们再二分订单数量,尝试满足mid个订单,(这个不会证明 QAQ)
因此我们ok函数这样写 ↓
IL bool ok(int now)//尝试满足now个订单
{
clear(delt);
for(RI i=1;i<=now;i++)
{
delt[s[i]]+=d[i];//s[i]为第i个订单起始天
delt[t[i]+1]-=d[i];//t[i]为第i个订单结束天.
}
for(RI i=1;i<=n;i++)
{
sum[i]=sum[i-1]+delt[i];//前缀和.
if(sum[i]>could[i])return false;
}
return true;
}
相信你随随便便也能切掉这个题了.
差分数组的话,一般并没有裸的考查,但是差分数组的思想啊,辅助啊,还是比较常用的qwq.
例如树状数组维护差分(到底是谁维护谁我也不是很清楚)qwq
(因为树状数组是维护的前缀和啊,所以可以一起用)
推荐一篇很好的文章(讲解树状数组与差分的结合使用)--->这里
Chanis写的也很好啊qwq
如果非要说差分数组的适用范围的话,
它适用于离线的区间修改问题,在线的话就去码 线段Tree 或 Tree状数组就好了 qwq
差分的板子题loj 洛谷
题解戳这里
p3943 星空 xor差分+最短路? (我也没有做啊 qwq
p3948 数据结构 一道差分的简单题 qwq.
这两个题我只码了第二题的代码
第一题有时间再做 qwq
其实主要是为了讲这个的qwq
2015,2016两年Noip对于树上差分都有考察 noip2015 运输计划 noip2016 天天爱跑步
这两个题涉及的知识点有着 树上差分+二分+LCA其实是我不太会qwq
所以在这里打算单纯地介绍一下树上差分并讲解一些例题.qwq
需要知道的树的性质:
树上任意两个点的路径唯一.
任何子节点的父亲节点唯一.(可以认为根节点是没有父亲的)
如果你认为你知道了这些你就能秒切这些树上差分的题,那你就太低估这个东西了!
树上差分的两种基本操作用到了LCA,不了解LCA的话可以去这里面学一下
类比于差分数组,树上差分利用的思想也是前缀和思想.(在这里应该是子树和思想.
当我们记录树上节点被经过的次数,记录某条边被经过的次数的时候.
如果每次强制dfs去标记的话,时间复杂度将高到爆炸!
因此我们引入了树上差分!
与树上差分在一起的使用的是
(这个应该不用过多解释
再度回到
这个时候
担忧: 万一我们再从
这样我们不就使得其父亲节点被经过了一次? 因此我们需要在
这样就达到了标记我们路径上的点的要求! 厉不厉害 (o゚▽゚)o tql!!
这样点的差分应该没什么问题了吧 ,有问题可以问我的哦 qwq (如果我会的话.)
既然我们已经get到了点的差分,那么我们边的差分也是很简单啦!
机房某dalao:"这不和点差分标记方式一样吗?不就是把边塞给点吗? 看我切了它!"
为这位大佬默哀一下 qwq.
的确,我们对边进行差分需要把边塞给点,但是,这里的标记并不是同点差分一样.
PS: 把边塞给点的话,是塞给这条边所连的深度较深的节点. (即塞给儿子节点
先请大家思考
好,时间到,有没有想到如何标记?(只要画图模拟一下就可以啦! 上图!
红色边为需要经过的边,绿色的数字代表经过次数
正常的话,我们的图是这样的.↓
但是由于我们把边塞给了点,因此我们的图应该是这样的↓
但是根据我们点差分的标记方式来看的话显然是行不通的,
这样的话我们会经过
因此考虑如何标记我们的点,来达到经过红色边的情况
聪明的你一定想到了,这样来标记
这样回溯的话,我们即可只经过图中红色边啦!(这里就不详细解释啦,原理其实相同 qwq
把边塞入点中的代码这样写.qwq(顺便在搜索的时候处理即可
void dfs(int u,int fa,int dis)
{
//u为当前节点,fa为当前节点的父亲节点,dis为从fa通向u的边的边权.
depth[u]=depth[fa]+1;
f[u][0]=fa;//相信写过倍增LCA的人都能看懂.
init[u]=dis;//这里是将边权赋给点.
for(int i=1;(1<<i)<=depth[u];i++)f[u][i]=f[f[u][i-1]][i-1];//预处理倍增数组.
for(int i=head[u];i;i=edge[i].u)
{
if(edge[i].v==fa)continue;
dfs(edge[i].v,u,edge[i].w);
}
//这个每个人的写法不一样吧.
//所以根据每个人的代码风格不一样,码出来的也不一样
}
代码会在下面统一发 qwq
先来一个简单题练练手 --->p3128 最大流
这个题应该算是树上差分的入门题
就是入门题qwq
题意简单概括一下 求被经过次数最多的点,(其实概括出来的话,这题就裸了.)
显然,裸的点差分.
所以请在课下切掉它qwq.
再来一个简单题练手 --->p3258 松鼠的新家
也是一个简单的树上差分的题.不过有一些小坑点.
读完题大家先思考
时间到。
简单分析 很明显,这是一道点差分.但是不同的是,我们需要在每个位置”中转“一下.
即从
因此我们经过这些节点次数会被重复计算,因此,我们需要将其
还要注意的是,当我们到达
代码中需要注意的位置也只有这里 这样↓
for(RI i=2;i<=n;i++)cnt[a[i]]--;
3.上点难度了 ----->p2680 运输计划
(可能是因为我太弱了 qwq
先感谢dalao的讲解 @GMPotlc
读完题,我们发现,这是一道边差分的题.
简单分析 于是建完边我们先dfs一遍预处理出根节点到每个节点的距离.并把边权塞给点。
预处理距离的话只需要再在dfs中加入一句即可
Dis[edge[i].v]=Dis[u]+edge[i].w;
然后我们可以计算出每条航道间的距离,类似这样
//
//*则$query[i].dis=Dis[x]+Dis[y]-2Dis[lca_{x,y}]$**
不能理解这个计算的话来看图 qwq.
图中给出的边均为从根节点到达某节点的距离.
颜色对应
我们发现,实际只要记录的距离仅为LCA下面的红色和绿色路径.
而我们重复经过了LCA上面的边两次."这没用啊"
因此只要减去2*
考虑:
我们需要将被经过次数最多,且边权最大的边删去.
这样能使我们所用总时间最大值尽可能小 (很明显 qwq
要求最大值最小? 很明显,我们想到了二分答案.
解决
既然想到了二分答案,那我们就二分这些路径的长度.(即工作时间.
如果一些路径长度大于当前二分的mid,我们就需要记录这些路径上的边其被经过次数.
(比mid小的路径一定已经合法,我们可以在mid时间内完成任务.)
假设路径长度大于mid的有num个
(我们找到被这些路径共同经过的最大的边权,删去它,使得这些路径长度都小于mid,那么这个mid就是合法的.
小细节:我们可以通过排序得到最大的路径长度,如果这条最长的路径减去被经过次数<=mid,那这个mid就是合法的,我们就可以去寻找更优解.
这里引用题解里的一句话
因为要求求最小时间, 然而可以根据单调性可以通过二分一个时间来判定这个时间能不能成立. 也就是通过二分答案将一个求答案的问题转化为
log_{2}t_{\max} 个判定性问题.
因此这个题就很简单了
PS:记得每次将标记数组清零.(因为大于mid的路径长度会变化.
(可能做法常数有些大,但是是可以过的.
(也可能是评测机看脸.第一次交T了一个点,第二次交就A掉了 qwq.
上面三个题的代码都在这里
树上差分的裸题还是比较少的(其实是我遇到的比较少吧 qwq.
因此树上差分与其他算法的结合考察还是比较多的
例如刚刚讲的运输计划就是一个 LCA+树上差分+二分.
(其实树上差分问题一定有LCA的 qwq)
总的来说,差分数组重点在于思想的运用.
而树上差分一般不会直接考裸题.
所以,我们需要掌握更多的算法. qwq
不会的可以问我 ,直到今年Noip我一直会在.
如果拿到省一的话,我会待的更久,拿不到就滚回去学文化课了 qwq
参考了一些dalao的博客,这里不一一列出了.qwq
(其实我忘了参考过哪些
再度感谢合伙人@GMPotlc