差分数组 and 树上差分

## 差分数组 ### 定义 百度百科中的[差分定义](https://baike.baidu.com/item/%E5%B7%AE%E5%88%86/10349967?fr=aladdin) //其实这完全和要讲的没关系 qwq 进去看了之后是不是觉得看不懂？ 那我简单概括一下qwq **差分数组de定义：**记录当前位置的数与上一位置的数的差值. **栗子**  容易发现的是,**$\sum_{j=1}^{i} b_j$即代表$a_i$ 的值.** $(\sum$ 即代表累加.) ### 思想 看到前面的$\sum$ 你一定会发现这是前缀和! 那你认为这是前缀和? 的确是qwq. 实际上这并不是真正意义上的前缀和. **前缀和的思想**是 根据元素与元素之间的并集关系(和的关系),**求出某些元素的和的值**.对应的为$\sum_{j=1}^{i} a_j $ 而差分的思想与此不同. **差分的思想**是 根据元素与元素之间的逻辑关系(大小关系),**求出某一位置元素的值**.对应的为$\sum_{j=1}^{i} b_j$ 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$代表$\sum_{j=1}^{i} b_j$ (其实就是代表$a[i]$ qwq > $sum_i$代表$\sum_{j=1}^{i} s_j$ 即代表前缀和. qwq 容易发现的是 $sum_r -sum_{l-1}=\sum_{i=l}^{r} s_i$ 什么不理解为什么是$l-1$？ 那我们把式子展开看 qwq $sum_r=s_1+s_2+\dots+s_{l-1}+s_{l}+s_{l+1}+\dots+s_r$ $sum_{l-1}=s_1+s_2+\dots+s_{l-2}+s_{l-1}$ 两个式子相减的话,我们得到的就是 $s_l+\dots+s_r$ 即$\sum_{i=l}^r s_i$啦! 而我们如果减去$sum_l$的话,就会多减去一个s_l,得到的值就不是$\sum_{i=l}^r s_i$ 了! ~~emmmm 差点跑去讲前缀和~~ 所以说我们可以在修改操作完成之后,$O(n)$的计算我们的$sum$数组,然后在询问的时候$O(1)$的输出了. 具体这个题的代码是这样的↓ #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; //输出即可. } } 刚刚**涉及到的用途**有 1. 快速处理区间加减操作：$O(1)$ 1. 询问区间和:$O(n)$处理$O(1)$查询. 你以为差分只有这么多用处吗? 利用**差分数组还能算出前缀和**,看式子变形!  所以说,上面的代码完全可以改一下,相信大家写出来应该会很容易. ~~(其实是我懒~~ qwq 差分还有其他用途这里并没有涉及到,所以还需要大家自己去发现去学习 ┓( ´∀｀ )┏ ### 例题 来一个 **差分+二分** 结合运用的题目 -->[p1083 借教室](https://www.luogu.org/problemnew/show/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 (因为树状数组是维护的前缀和啊,所以可以一起用) 推荐一篇很好的文章(讲解树状数组与差分的结合使用)--->[这里](http://www.cnblogs.com/RabbitHu/p/BIT.html) [Chanis](https://www.luogu.org/blog/Chanis/super-BIT)写的也很好啊qwq 如果非要说**差分数组的适用范围**的话, 它适用于**离线的区间修改问题**,在线的话就去码 线段Tree 或 Tree状数组就好了 qwq ### 课下作业 差分的板子题[loj](https://loj.ac/problem/2332)　[洛谷](https://www.luogu.org/problemnew/show/AT2442) 题解戳[这里](https://rpdreamer.blog.luogu.org/at2442) [p3943 星空](https://www.luogu.org/problemnew/show/P3943) xor差分+最短路? (我也没有做啊 qwq [p3948 数据结构](https://www.luogu.org/problemnew/show/P3948) 一道差分的简单题 qwq. 这两个题我只码了[第二题的代码](https://www.luogu.org/paste/avct2k5l) 第一题有时间再做 qwq ## 树上差分 其实主要是为了讲这个的qwq 2015,2016两年Noip对于树上差分都有考察 [noip2015 运输计划](https://www.luogu.org/problemnew/show/P2680) [noip2016 天天爱跑步]( https://www.luogu.org/problemnew/show/P1600) 这两个题涉及的知识点有着 **树上差分+二分+LCA$\dots$**,这是一些进阶的考查 ~~其实是我不太会qwq~~ 所以在这里打算~~单纯地~~介绍一下树上差分并讲解一些例题.qwq ### 前置知识 需要知道的**树的性质**: 1. 树上任意两个点的路径唯一. 2. 任何子节点的父亲节点唯一.(可以认为根节点是没有父亲的) 如果你认为你知道了这些你就能秒切这些树上差分的题,那你就太低估这个东西了! 树上差分的**两种基本操作用到了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$ $\vdots$ $\vdots$ $\vdots$ 好,时间到,有没有想到如何标记?(只要画图模拟一下就可以啦! 上图! > 红色边为需要经过的边,绿色的数字代表经过次数 正常的话,我们的图是这样的.↓  但是由于我们把边塞给了点,因此我们的图应该是这样的↓  但是根据我们点差分的标记方式来看的话显然是行不通的, 这样的话我们会经过$father_{LCA}--> LCA$这一路径. 因此考虑如何标记我们的点,来达到经过红色边的情况 聪明的你一定想到了,这样来标记 $cnt_s++$ ， $cnt_t ++$ ，$cnt_{LCA}-=2$ 这样回溯的话,我们即可只经过图中红色边啦!(这里就不详细解释啦,原理其实相同 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 1. 先来一个简单题练练手 --->[p3128 最大流](https://www.luogu.org/problemnew/show/P3128) 这个题应该算是树上差分的入门题 ~~就是入门题qwq~~ **题意简单概括一下** 求被经过次数最多的点,(其实概括出来的话,这题就裸了.) 显然,裸的点差分. 所以请在课下切掉它qwq. 2. 再来一个简单题练手 --->[p3258 松鼠的新家](https://www.luogu.org/problemnew/show/P3258) 也是一个简单的树上差分的题.不过有一些小坑点. 读完题大家先思考$5s$ $\vdots$ 时间到。 **简单分析** 很明显,这是一道点差分.但是不同的是,我们需要在每个位置”中转“一下. 即从 $a_1-->a_2$ ，$a_2-->a_3$ ，$a_3-->a_4$ $\dots$我们会重复经过$a_2$，$a_3$，$\dots$这一些点. 因此我们经过这些节点次数会被重复计算,因此,我们需要将其$--$ 还要注意的是,当我们到达$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](https://www.luogu.org/space/show?uid=87956) 读完题,我们发现,这是一道边差分的题. **简单分析** 于是建完边我们先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. 上面三个题的代码都在[这里](https://www.luogu.org/paste/1uqw6p54) ### 小结 树上差分的裸题还是比较少的(其实是我遇到的比较少吧 qwq. 因此树上差分与其他算法的结合考察还是比较多的 例如刚刚讲的运输计划就是一个 LCA+树上差分+二分. (其实树上差分问题一定有LCA的 qwq) ## BB in last 总的来说,差分数组重点在于思想的运用. 而树上差分一般不会直接考裸题. 所以,我们需要掌握更多的算法. qwq 不会的可以问我 ,直到今年Noip我一直会在. 如果拿到省一的话,我会待的更久,拿不到就滚回去学文化课了 qwq --- 参考了一些dalao的博客,这里不一一列出了.qwq ~~(其实我忘了参考过哪些~~ 再度感谢**合伙人[@GMPotlc](https://www.luogu.org/space/show?uid=87956)**