[洛谷日报第76期]差分数组 and 树上差分
洛谷科技2018-10-26 13:15
差分数组
定义
百度百科中的差分定义（https://baike.baidu.com/item/%E5%B7%AE%E5%88%86/10349967?fr=aladdin）//其实这完全和要讲的没关系 qwq
进去看了之后是不是觉得看不懂？
那我简单概括一下qwq
差分数组de定义：记录当前位置的数与上一位置的数的差值.
栗子
容易发现的是,∑ b[j](j = 1 to i)即代表a[i] 的值. (∑ 即代表累加.)
思想
看到前面的∑ 你一定会发现这是前缀和!
那你认为这是前缀和? 的确是qwq.
实际上这并不是真正意义上的前缀和.
前缀和的思想是 根据元素与元素之间的并集关系(和的关系),求出某些元素的和的值.对应的为∑ a[j](j = 1 to i)
而差分的思想与此不同.
差分的思想是 根据元素与元素之间的逻辑关系(大小关系),求出某一位置元素的值.对应的为∑ b[j](j = 1 to i)
What?不懂?看下面
继续捡起刚刚的栗子.
有没有发现不同之处 ( ω )
差分数组有什么用?
先看一道题,
有n个数。
m次操作,每一次操作,给定l,r,del.将l~r区间的所有数增加del；
最后有q个询问,给你 l,r ,每一次询问求出l~r的区间和。
PS： 先进行m个修改操作,后进行查询操作.
如果你是一个巨佬,你会"woc,线段树裸题!" "woc,树状数组裸题!"
然而,今天我要BB的不是这些东西.
是差分数组的运用!
有没有想法? 没有的话那就我来有也是我来
考虑我们差分数组记录的是什么,它记录的是当前位置的数与上一个数的差值.
如果我们在差分数组的 b_x减去del 在b_{y+1}位置处加上del,就能达到整个区间修改的操作.
什么?不相信? 那我们来个栗子(要糖炒的
还是刚开始的栗子.
这样是不是达到了区间修改操作,是不是! "是!,tql!!"
这样我们就能做到O(1)修改啦!
我们再定义两个数组(先不要忘记我们的差分数组为b_i
s_i代表∑ b[j](j = 1 to i) (其实就是代表a[i] qwq
sum_i代表∑ s[j](j = 1 to i) 即代表前缀和. qwq
容易发现的是 sum_r -sum_{l-1}=∑ s[j](j = 1 to i)
什么不理解为什么是l-1？
那我们把式子展开看 qwq
emmmm 差点跑去讲前缀和
所以说我们可以在修改操作完成之后,O(n)的计算我们的sum数组,然后在询问的时候O(1)的输出了.
具体这个题的代码是这样的↓
刚刚涉及到的用途有
快速处理区间加减操作：O(1)询问区间和:O(n)处理O(1)查询.
你以为差分只有这么多用处吗?
利用差分数组还能算出前缀和,看式子变形!
所以说,上面的代码完全可以改一下,相信大家写出来应该会很容易. (其实是我懒 qwq
差分还有其他用途这里并没有涉及到,所以还需要大家自己去发现去学习 ┓( ｀ )┏
例题
来一个 差分+二分 结合运用的题目 -->洛谷P1083 借教室（https://www.luogu.org/problemnew/show/P1083）
看完题目了没? 有没有思路?
想一下,
在 一个订单的起始天+要借的教室数量, 并在该订单结束的那一天的下一天减去要借的教室数量
这样我们再维护一下前缀和,这就样就能知道这些天中,我们借了多少教室! 是不是很巧妙qwq
然后我们再二分订单数量,尝试满足mid个订单,(这个不会证明 QAQ)
因此我们ok函数这样写 ↓
相信你随随便便也能切掉这个题了.
小结
差分数组的话,一般并没有裸的考查,但是差分数组的思想啊,辅助啊,还是比较常用的qwq.
例如树状数组维护差分(到底是谁维护谁我也不是很清楚)qwq
(因为树状数组是维护的前缀和啊,所以可以一起用)
推荐一篇很好的文章(讲解树状数组与差分的结合使用)--->http://www.cnblogs.com/RabbitHu/p/BIT.html
这篇 https://www.luogu.org/blog/Chanis/super-BIT 写的也很好啊qwq
如果非要说差分数组的适用范围的话,
它适用于离线的区间修改问题,在线的话就去码 线段Tree 或 Tree状数组就好了 qwq
树上差分
其实主要是为了讲这个的qwq
2015,2016两年Noip对于树上差分都有考察（https://www.luogu.org/problemnew/show/P2680）
noip2015 运输计划(P2680)noip2016 天天爱跑步(P1600)
这两个题涉及的知识点有着 树上差分+二分+LCA…,这是一些进阶的考查 其实是我不太会qwq
所以在这里打算单纯地介绍一下树上差分并讲解一些例题.qwq
前置知识
需要知道的树的性质:
树上任意两个点的路径唯一.任何子节点的父亲节点唯一.(可以认为根节点是没有父亲的)
如果你认为你知道了这些你就能秒切这些树上差分的题,那你就太低估这个东西了!
树上差分的两种基本操作用到了LCA,不了解LCA的话可以去这里面学一下（https://www.luogu.org/problemnew/show/P3379）
思想
类比于差分数组,树上差分利用的思想也是前缀和思想.(在这里应该是子树和思想.
当我们记录树上节点被经过的次数,记录某条边被经过的次数的时候.
如果每次强制dfs去标记的话,时间复杂度将高到爆炸!
因此我们引入了树上差分!
与树上差分在一起的使用的是DFS，因为在回溯的时候,我们可以计算出子树的大小.
(这个应该不用过多解释
定义数组
cnt_i为节点i被经过的次数.
基本操作
1.点的差分
这个比较简单,所以先讲这个qwq
例如,我们从 s-->t ,求这条路径上的点被经过的次数.
很明显的,我们需要找到他们的LCA,(因为这个点是中转点啊qwq.
我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--;
可能读着会有些难理解,所以我准备了一个图qwq
绿色的数字代表经过次数.
直接去标记的话,可能会T到不行,但是我们现在在讲啥?树上差分啊!
根据刚刚所讲,我们的标记应该是这样的↓
考虑：我们搜索到s,向上回溯.
下面以u表示当前节点,son_i代表i的儿子节点.(如果一些son不给出下标,即代表当前节点u的儿子
每个u统计它的子树大小,顺着路径标起来.(即cnt[u]+=cnt[son])
我们会发现第一次从s回溯到它们的LCA时候,cnt[LCA]+=cnt[son[LCA]]
cnt[LCA]=0! "不是LCA会被经过一次嘛,为什么是0!"
别急,我们继续搜另一边.
继续：我们搜索到t,向上回溯.
依旧统计每个u的子树大小cnt[u]+=cnt[son]
再度回到LCA 依旧 是cnt[LCA]+=cnt[son[LCA]]
这个时候 cnt[LCA]=1 这就达到了我们要的效果 (是不是特别优秀 ( ω )
担忧： 万一我们再从LCA向上回溯的时候使得其父亲节点的子树和为1怎么办?
这样我们不就使得其父亲节点被经过了一次? 因此我们需要在cnt[faher(lca)]--
这样就达到了标记我们路径上的点的要求! 厉不厉害 (o▽)o tql!!
这样点的差分应该没什么问题了吧 ,有问题可以问我的哦 qwq (如果我会的话.)
2.边的差分
既然我们已经get到了点的差分,那么我们边的差分也是很简单啦!
机房某dalao:"这不和点差分标记方式一样吗?不就是把边塞给点吗? 看我切了它!"
为这位大佬默哀一下 qwq.
的确,我们对边进行差分需要把边塞给点,但是,这里的标记并不是同点差分一样.
PS: 把边塞给点的话,是塞给这条边所连的深度较深的节点. (即塞给儿子节点
先请大家思考5s
…
…
…
好,时间到,有没有想到如何标记?(只要画图模拟一下就可以啦! 上图!
红色边为需要经过的边,绿色的数字代表经过次数
正常的话,我们的图是这样的.↓
但是由于我们把边塞给了点,因此我们的图应该是这样的↓
但是根据我们点差分的标记方式来看的话显然是行不通的,
这样的话我们会经过father[LCA]--> LCA这一路径.
因此考虑如何标记我们的点,来达到经过红色边的情况
聪明的你一定想到了,这样来标记
cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2
这样回溯的话,我们即可只经过图中红色边啦!(这里就不详细解释啦,原理其实相同 qwq
把边塞入点中的代码这样写.qwq(顺便在搜索的时候处理即可
例题选讲
代码会在下面统一发 qwq
先来一个简单题练练手 --->洛谷P3128 最大流（https://www.luogu.org/problemnew/show/P3128）这个题应该算是树上差分的入门题就是入门题qwq题意简单概括一下求被经过次数最多的点,(其实概括出来的话,这题就裸了.)显然,裸的点差分.所以请在课下切掉它qwq.再来一个简单题练手 --->洛谷P 松鼠的新家（https://www.luogu.org/problemnew/show/P3258）也是一个简单的树上差分的题.不过有一些小坑点.读完题大家先思考5s…时间到。简单分析很明显,这是一道点差分.但是不同的是,我们需要在每个位置”中转“一下.即从 a_1-->a_2 ，a_2-->a_3 ，a_3-->a_4 …我们会重复经过a_2，a_3，…这一些点.因此我们经过这些节点次数会被重复计算,因此,我们需要将其--还要注意的是,当我们到达a_n这一位置的时候,小熊会吃饭 qwq ,即在这里不会有糖果吃. 所以这个位置的经过次数也需要--.代码中需要注意的位置也只有这里 这样↓ for(RI i=2;i<=n;i++)cnt[a[i]]--;3.上点难度了 ----->p2680 运输计划（https://www.luogu.org/problemnew/show/P2680）(可能是因为我太弱了 qwq先感谢dalao的讲解 @GMPotlc读完题,我们发现,这是一道边差分的题.简单分析于是建完边我们先dfs一遍预处理出根节点到每个节点的距离.并把边权塞给点。预处理距离的话只需要再在dfs中加入一句即可Dis[edge[i].v]=Dis[u]+edge[i].w;然后我们可以计算出每条航道间的距离,类似这样//query[i].dis代表第i个询问两航道之间的距离//则query[i].dis=Dis[x]+Dis[y]-2*Dis[lca_{x,y}]不能理解这个计算的话来看图 qwq.
图中给出的边均为从根节点到达某节点的距离.
颜色对应
我们发现,实际只要记录的距离仅为LCA下面的红色和绿色路径.
而我们重复经过了LCA上面的边两次."这没用啊"
因此只要减去2*Dis_{LCA}即可.
考虑：
我们需要将被经过次数最多,且边权最大的边删去.
这样能使我们所用总时间最大值尽可能小 (很明显 qwq
要求最大值最小? 很明显,我们想到了二分答案.
解决
既然想到了二分答案,那我们就二分这些路径的长度.(即工作时间.
如果一些路径长度大于当前二分的mid,我们就需要记录这些路径上的边其被经过次数.
(比mid小的路径一定已经合法,我们可以在mid时间内完成任务.)
假设路径长度大于mid的有num个
(我们找到被这些路径共同经过的最大的边权,删去它,使得这些路径长度都小于mid,那么这个mid就是合法的.
小细节:我们可以通过排序得到最大的路径长度,如果这条最长的路径减去被经过次数<=mid,那这个mid就是合法的,我们就可以去寻找更优解.
这里引用题解里的一句话
因为要求求最小时间, 然而可以根据单调性可以通过二分一个时间来判定这个时间能不能成立.也就是通过二分答案将一个求答案的问题转化为log_{2}t_{\max}个判定性问题.
因此这个题就很简单了
PS:记得每次将标记数组清零.(因为大于mid的路径长度会变化.
(可能做法常数有些大,但是是可以过的.
(也可能是评测机看脸.第一次交T了一个点,第二次交就A掉了 qwq.
上面三个题的代码都在这里
小结
树上差分的裸题还是比较少的(其实是我遇到的比较少吧 qwq.
因此树上差分与其他算法的结合考察还是比较多的
例如刚刚讲的运输计划就是一个 LCA+树上差分+二分.
(其实树上差分问题一定有LCA的 qwq)
BB in last
总的来说,差分数组重点在于思想的运用.
而树上差分一般不会直接考裸题.
所以,我们需要掌握更多的算法. qwq
不会的可以问我 ,直到今年Noip我一直会在.
如果拿到省一的话,我会待的更久,拿不到就滚回去学文化课了 qwq
参考了一些dalao的博客,这里不一一列出了.qwq(其实我忘了参考过哪些
再度感谢合伙人[@GMPotlc]
本文发布于洛谷日报，特约作者：顾z
原文地址：https://rpdreamer.blog.luogu.org/ci-fen-and-shu-shang-ci-fen
举报/反馈
0
0
收藏
分享
