算法合集之RMQ与LCA问题.pptx

RMQ&LCA问题问题湖南省长郡中学 郭华阳全文总揽全文总揽l问题的提出l问题的解决l问题的应用 I.问题的提出问题的提出问题的提出lLCA：基于有根树最近公共祖先问题lLCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先问题的提出问题的提出lRMQ：区间最小值询问问题lRMQ（A，i，j）：对于线性序列A中，询问区间i，j上的最小值l特别的，若线性序列A任意两相邻元素相差为1，那么建立在A上的RMQ称为1RMQRMQ&LCA在信息学竞赛中在信息学竞赛中l各种竞赛试题中，如上海2003年省选的登山、2002年POI的商务旅行等，都是这类问题的应用及扩展l熟练的掌握及解决RMQ&LCA问题，对于研究和竞赛都是十分重要的 II.问题的解决RMQ&LCA问题的解决问题的解决l在研究人员的努力下，RMQ&LCA问题已经获得了比较完善的解决方案，这里我们只列出一些常用算法的适用范围以及他们的时空复杂度：算法名称针对问题时间消耗空间消耗ST算法一般RMQ问题O(Nlog2N)Tarjan算法LCA问题O(N)1RMQ算法1RMQ问题O(N)注：N表示问题规模，Q表示询问次数RMQ&LCA问题的解决问题的解决l我们以O(f(N)O(g(N)描述一个在线算法，在O(f(N)的时间内完成预处理，在O(g(N)的时间内完成一次询问l以O(f(N)+g(N)Q)描述一个离线算法的时间消耗算法名称针对问题时间消耗空间消耗ST算法一般RMQ问题O(Nlog2N)-O(1)O(Nlog2N)Tarjan算法LCA问题O(Na(N)+Q)O(N)1RMQ算法1RMQ问题O(N)-O(1)O(N)注：N表示问题规模，Q表示询问次数RMQ&LCA问题的解决问题的解决l这些算法各自具有特点，但是针对问题过于狭窄。下文中我们将会看到，RMQ与LCA问题是可以互相转化的，这就大大扩宽了以下算法的应用面算法名称针对问题时间消耗空间消耗ST算法一般RMQ问题O(Nlog2N)-O(1)O(Nlog2N)Tarjan算法LCA问题O(Na(N)+Q)O(N)1RMQ算法1RMQ问题O(N)-O(1)O(N)注：N表示问题规模，Q表示询问次数RMQ向向LCA的转化的转化l考察一个长度为N的序列A，按照如下方法将其递归建立为一棵树：1)设序列中最小值为Ak，建立优先级为Ak的根节点Tk；2)将A(1k1)递归建树作为Tk的左子树；3)将A(k+1N)递归建树作为Tk的右子树；l不难发现，这棵树是一棵优先级树A =(7 5 8 1 10)我们以A序列为例建立树TA =(7 5 8 1 10)1将最小元素1作为根节点左右分别建树A =(7 5 8 1 10)110右子树只有一个结点，即10A =(7 5 8 1 10)110左子树有三个结点7、5、8A =(7 5 8 1 10)1105左子树有三个结点7、5、8将最小元素5作为根节点左右分别建树A =(7 5 8 1 10)110578元素5的左右子树都只有一个结点，分别是7、8A =(7 5 8 1 10)110578这样我们便得到了树TRMQ向向LCA的转化的转化l对于RMQ(A，i，j)：1)设序列中最小值为Ak，若ki,j，那么答案为k；2)若k j，那么答案为RMQ(A1.k-1，i，j)；3)若k 0，则存在一条边(u,v)P T引入最小生成森林引入最小生成森林l引理一：任意询问可以在G的最小生成森林中找到最优解l证明（续）：考察这条边(u,v)：引入最小生成森林引入最小生成森林l引理一：任意询问可以在G的最小生成森林中找到最优解l证明（续）：考察这条边(u,v)：l根据最小生成森林的性质，存在一条只有树边构成的路径P0连接u、v两点，并且P0的花费不大于(u,v)的花费引入最小生成森林引入最小生成森林l引理一：任意询问可以在G的最小生成森林中找到最优解l证明（续）：考察这条边(u,v)：l根据最小生成森林的性质，存在一条只有树边构成的路径P0连接u、v两点，并且P0的花费不大于(u,v)的花费l将P中(u,v)替换为路径P0，P的总花费不增且(P)减小引入最小生成森林引入最小生成森林l引理一：任意询问可以在G的最小生成森林中找到最优解l证明（续）：由于(P)0，所以可以在有限次替换后将P变成一条T中的路径 这就证明了该引理引入最小生成森林引入最小生成森林l引理一：任意询问可以在G的最小生成森林中找到最优解l根据引理，我们只需要保存所有树边即可，这样边数下降到O(N)级别，第一个问题被解决。完成询问完成询问l我们来考虑第二个问题l注意到最小生成森林中任意两点之间的路径是唯一的。我们可以采用DFS找出该路径中的关键边，时间消耗为O(N)l考虑到N=1000、Q=105，这样的时间复杂度仍然不能很好解决本题深入思考深入思考l询问树上两点之间路径上的最大边，这种问题可以使用动态树等工具实现，但是都过于复杂。l为了找出一个简单、实用的算法，我们需要仔细的研究最小生成森林的性质lKruskal算法是建立最小生成森林中为我们所熟知的算法，以下我们将模拟一次Kruskal算法的执行123456152673410我们使用Kruskal算法生成上图的最小生成森林，将所有边按照权值从小到大加入123456152673410加入边(1,2)为树边注意到Query(1,2)的关键边为(1,2)123456152673410加入边(1,3)为树边注意到Query(1|2,3)的关键边为(1,3)123456152673410加入边(4,6)为树边注意到Query(4,6)的关键边为(4,6)123456152673410加入边(5,6)为树边注意到Query(4|6,5)的关键边为(5,6)123456152673410加入边(2,3)注意到已存在路径(2,1)(1,3)，所以(2,3)非树边123456152673410加入边(3,4)为树边注意到Query(1|2|3,4|5|6)的关键边为(3,4)123456152673410此时，我们已经的到了最小生成森林T更重要的是，我们也已经得到了所有询问的回答！重要引理的发现重要引理的发现l对Kruskal过程仔细思考，我们得出关键：l引理二：l任意两点u、v间最短路径的关键边，为执行Kruskal算法中第一次将此两点连通的树边！Kruskal生成顺序森林生成顺序森林l如何适当的应用引理二呢？所有的树边和结点需要被有机的结合起来，这里我们使用Kruskal生成顺序森林（简称顺序森林）l仍然考虑下图：Kruskal生成顺序森林生成顺序森林l顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点iKruskal生成顺序森林生成顺序森林l顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点iV1V2V3V4V5V6Kruskal生成顺序森林生成顺序森林l树边Ei被加入时，该边所连接的两个连通块在顺序森林中必然是两棵树V1V2V3V4V5V6Kruskal生成顺序森林生成顺序森林l建立顺序森林结点与Ei相对应，其左右孩子分别为两个连通块对应树的根结点V1V2V3V4V5V6Kruskal生成顺序森林生成顺序森林l我们模拟将所有的树边依次加入：V1V2V3V4V5V6Kruskal生成顺序森林生成顺序森林l添加树边(1,2)，将原图结点1、2合并为一个连通块；我们建立顺序森林结点E1，两个儿子为V1、V2V1V2V3V4V5V6E1Kruskal生成顺序森林生成顺序森林l添加树边(1,3)，将原图结点1、2、3合并为一个连通块；我们建立顺序森林结点E2，两个儿子为E1、V3V1V2V3V4V5V6E1E2Kruskal生成顺序森林生成顺序森林l类似的添加树边(4,6)时，建立顺序森林结点E3，两儿子为V4、V6V1V2V3V4V5V6E1E2E3Kruskal生成顺序森林生成顺序森林l添加树边(5,6)时，建立顺序森林结点E4，两儿子为V5、E3V1V2V3V4V5V6E1E2E3E4Kruskal生成顺序森林生成顺序森林l添加树边(3,4)时，建立顺序森林结点E5，两儿子为E2、E4V1V2V3V4V5V6E1E2E3E4E5Kruskal生成顺序森林生成顺序森林l我们得到了图G的最小生成顺序森林V1V2V3V4V5V6E1E2E3E4E5引入引入LCA解决问题！解决问题！l不难发现，Query(Vi,Vj)即为顺序森林中他们的最近公共祖先！l根据已有的成果，我们可以在O(N+Q)的时间内完成两次删边操作之间的所有询问l可以采用Tarjan算法解决水管局长水管局长l让我们总结以上的算法流程：1)生成结束时的最小生成森林和顺序森林；2)从后往前完成操作：对于删边操作，重新生成最小生成森林和顺序森林；对于连续的询问操作，将其作为离线LCA询问在顺序森林上处理；3)输出答案；时间复杂度时间复杂度l在我的论文中以下结论被给出：1)生成、维护最小生成森林和顺序树总时间花费为O(Mlog2M+DNa(N)2)询问可以在O(Q+ND)的时间内解决l总的时间复杂度为：O(Mlog2M+DNa(N)+Q)小结小结l我们先发现了解题的关键所在：l边数过多（数据规模大）l求解时间复杂度过高l针对第一点，我们引入最小生成森林l针对第二点，我们充分利用了经典算法l在已有的问题模型和算法上，合理的转化，最终得到了本题的解决方案总结总结lRMQ&LCA问题作为经典问题无论在算法学习上还是实际应用中都发挥了巨大的作用l解决问题研究算法时，恰当的引入经典问题和经典算法，无疑会大大加大我们的解题速度和精度！l站在巨人的肩膀上，我们才能看得更高、更远！谢谢！谢谢！敬请批评指正！引入最小生成森林的时间花费引入最小生成森林的时间花费l时间复杂度分为两个部分：l生成最小生成森林的时间消耗l维护最小生成森林的时间消耗l生成的复杂度由经典的Kruskal算法给出：O(Mlog2M)l以下主要讨论维护的时间消耗引入最小生成森林的时间花费引入最小生成森林的时间花费l考察题目给出的删边操作l若需删除的边非树边，那么不需要进行维护l否则，我们需要枚举另一条边来进行补充，枚举量高达O(M)！l正难则反，若是向图中添加一条新的边呢？l注意到一个重要的性质，原非树边在添加新边后仍然为非树边！l算法只需在原树边与新边中找出新的最小生成森林引入最小生成森林的时间花费引入最小生成森林的时间花费l将删边操作转化为添边操作，从后往前执行所有操作即可l综上，算法只需要在不超过N条边中建立最小生成森林，复杂度为O(Na(N)l注意到，最小顺序森林的生成与最小生成森林是同步的，所以亦可以在O(Na(N)的时间内完成完成询问的时间花费完成询问的时间花费l按照添边操作，可以把操作序列分为很多段：l对于连续两个添边操作之间的询问操作，我们可以采取经典算法解决，时间花费为O(N+Q)。总时间复杂度为：O(ND+Q)l添边操作l询问操作ll询问操作l添边操作l询问操作ll询问操作lSparse Table算法算法l一般RMQ的Sparse Table（ST）算法是基于倍增思想设计的O(Nlog2N)O(1)在线算法l算法记录从每个元素开始的连续的长度为2k的区间中元素的最小值，并以在常数时间内解决询问Sparse Table算法算法l对于RMQ（A，i，j），我们可以找到两段极大的长度为2的幂的区间（如图）覆盖i，jl由已经计算的结果在O(1)的时间内解决询问ijA2k2kSparse Table算法算法l利用倍增思想，在O(Nlog2N)的时间内，我们可以预处理所有长度为2的幂的区间的最小值l我们可以用O(N)的时间处理长度为1的区间l对于长度为2k的区间的最小值，可以由两个长度为2k-1的区间的最小值得到（如图）2k2k-12k-1Tarjan算法算法l解决LCA问题的Tarjan算法利用并查集在一次DFS（深度优先遍历）中完成所有询问。它是时间复杂度为O(Na(N)+Q)的离线算法Tarjan算法算法l考察树T中所有与结点u有关的询问(u,v)uvp1p2对于子树对于子树u u中的结点中的结点v v，满足，满足LCA(u,v)=vLCA(u,v)=v对于子树对于子树p1p1而非子树而非子树u u中的结点中的结点v v，满足，满足LCA(u,v)=p1LCA(u,v)=p1对于子树对于子树p2p2而非子树而非子树p1p1中的结点中的结点v v，满足，满足LCA(u,v)=p2LCA(u,v)=p2vvTarjan算法算法up1p2算法算法DFSDFS有根树有根树T T，定义从根节点到当前正在，定义从根节点到当前正在遍历的结点遍历的结点u u的路径为活跃路径的路径为活跃路径P P对于每个已经遍历过的结点对于每个已经遍历过的结点x x，我们使用并查，我们使用并查集将其连接到集将其连接到P P上距离其最近的结点上距离其最近的结点F(x)F(x)正在遍历F(x)F(x)F(x)Tarjan算法算法up1p2正在遍历记录与记录与u u有关的询问集合为有关的询问集合为Q(u)Q(u)对于对于Q(u)Q(u)中的任意一组询问中的任意一组询问LCA(u,v)LCA(u,v)，如果，如果v v已经遍历过，那么答案即为已经遍历过，那么答案即为F(v)F(v)我们只需要维护当前所有以遍历结点的我们只需要维护当前所有以遍历结点的F F即可即可up1p2正在遍历记录与记录与u u有关的询问集合为有关的询问集合为Q(u)Q(u)1)1)第一次遍历结点第一次遍历结点u u时，有时，有F(u)=uF(u)=u；2 2）遍历完子树）遍历完子树u u后，子树后，子树u u内任意结点内任意结点w w均有均有F(w)=uF(w)=u；回溯回结点；回溯回结点p1p1时，子时，子树树u u内任意结点内任意结点w w均有均有F(w)=p1F(w)=p1，使，使用并查集完成即可；用并查集完成即可；FTarjan算法算法Tarjan算法算法l算法流程：Tarjan_DFS(u)1)F(u)u；2)For(u,v)Q(u)do Answer(u,v)F(v)3)For v son(u)a)Tarjan_DFS(v)；b)F(v)u；注：此处F采用并查集实现1RMQ算法算法l算法的核心思想在于分块：l以L=log2N/2块长把B划分为M=N/L段，记录第k块的最小元素为BlockMin(k)，把M块的最小值组成序列Blocks，利用分块思想，我们可以把询问分为两个部分询问：log2N/2BlockMin(1)BlockMin(M)M=N/L1)连续的BlockMin取最小值，即Block-RMQ；2)两端块中某一部分取最小值，即In-RMQ；Block-RMQlog2N/2QueryIn-RMQ这两个问题都可以O(N)O(1)内实现In-RMQ1RMQ算法算法Block-RMQlBlock-RMQ采用ST算法来实现，根据前文所讨论的，时间复杂度为O(Mlog2M)O(1)l因为Mlog2M 2N/log2N*log2N=O(N)，所以Block-RMQ的复杂度不大于O(N)O(1)In-RMQa)B中任意两个相邻数为1，所以本质不同的块至多有2L-1种；b)对于每一种块上的询问至多只有O(L2)种；l所以本质不同的询问数至多有O(2L-1L2)=O(N0.5log22N)O(N)l完成In-RMQ只需预处理所有本质不同的询问对应作答即可，时间复杂度为O(N)-O(1)1RMQ算法算法l因为LCA问题可以转化为生成序列的RMQ问题且问题规模不变，所以LCA问题可以在O(N)-O(1)的时间内解决；l因为RMQ问题可以转化为LCA问题且问题规模不变，所以RMQ问题可以在O(N)-O(1)的时间内解决；