《rmq与lca问题》

《《rmq与lca问题》》由会员分享，可在线阅读，更多相关《《rmq与lca问题》（80页珍藏版）》请在金锄头文库上搜索。

1、RMQ&LCA问题,问题的提出,LCA：基于有根树最近公共祖先问题 LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先,问题的提出,RMQ：区间最小值询问问题 RMQ（A，i，j）：对于线性序列A中，询问区间i，j上的最小值 特别的，若线性序列A任意两相邻元素相差为1，那么建立在A上的RMQ称为1RMQ,RMQ&LCA问题的解决,在研究人员的努力下，RMQ&LCA问题已经获得了比较完善的解决方案，这里我们只列出一些常用算法的适用范围以及他们的时空复杂度：,注：N表示问题规模，Q表示询问次数,RMQ&LCA问题的解决,我们以O(f(N) O(g(N)描述

2、一个在线算法，在O(f(N)的时间内完成预处理，在O(g(N)的时间内完成一次询问 以O(f(N) + g(N)Q)描述一个离线算法的时间消耗,注：N表示问题规模，Q表示询问次数,RMQ&LCA问题的解决,这些算法各自具有特点，但是针对问题过于狭窄。下文中我们将会看到，RMQ与LCA问题是可以互相转化的，这就大大扩宽了以下算法的应用面,注：N表示问题规模，Q表示询问次数,RMQ向LCA的转化,考察一个长度为N的序列A，按照如下方法将其递归建立为一棵树： 设序列中最小值为Ak，建立优先级为Ak的根节点Tk； 将A(1k1)递归建树作为Tk的左子树； 将A(k+1N)递归建树作为Tk的右子树； 不

3、难发现，这棵树是一棵优先级树,A = (7 5 8 1 10),我们以A序列为例建立树T,A = (7 5 8 1 10),1,将最小元素1作为根节点 左右分别建树,A = (7 5 8 1 10),1,1,0,右子树只有一个结点，即10,A = (7 5 8 1 10),1,1,0,左子树有三个结点7、5、8,A = (7 5 8 1 10),1,1,0,5,左子树有三个结点7、5、8 将最小元素5作为根节点 左右分别建树,A = (7 5 8 1 10),1,1,0,5,7,8,元素5的左右子树都只有一个结点，分别是7、8,A = (7 5 8 1 10),1,1,0,5,7,8,这样我们

4、便得到了树T,RMQ向LCA的转化,对于RMQ(A，i，j)： 设序列中最小值为Ak，若ki, j，那么答案为k； 若k j，那么答案为RMQ(A1k-1，i，j)； 若k i，那么答案为RMQ(AK+1N，i，j)； 不难发现RMQ(A，i，j) = LCA(T，i，j)！ 这就证明了RMQ问题可以转化为LCA问题,LCA向RMQ的转化,对有根树T进行DFS，将遍历到的结点按照顺序记下，我们将得到一个长度为2N 1的序列，称之为T的欧拉序列F 每个结点都在欧拉序列中出现，我们记录结点u在欧拉序列中第一次出现的位置为pos(u),1,2,3,4,5,6,深度0,深度1,深度2,1,1,2,5,

5、2,6,2,1,3,4,1,欧拉序列F：,深度序列B：0 1 2 1 2 1 0 1 0 1 0,Pos (u)：1 2 8 10 3 5,LCA向RMQ的转化,根据DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u, v)有且仅有一次，且深度是深度序列Bpos(u)pos(v)中最小的 即LCA(T, u, v) = RMQ(B, pos(u), pos(v)，并且问题规模仍然是O(N)的,LCA向RMQ的转化,根据DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u, v)有且仅有一次，且深度是深度序列Bpos(u)po

6、s(v)中最小的 这就证明了LCA问题可以转化成RMQ问题 LCA与RMQ问题可以互相转化，并且可以在O(N)的时间内完成！,RMQ&LCA算法关系图,一般RMQ问题,1RMQ问题,LCA问题,ST算法,Tarjan算法,1RMQ算法,O(N),O(N),III. 问题的应用,问题的应用,RMQ&LCA问题在算法研究及信息学竞赛中都发挥着十分重要的作用，它主要是以一种经典算法及解题思想的形式出现 本文主要以讨论一道例题： 水管局长（2006年冬令营试题）,水管局长（原题）,SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能

7、要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。 在 处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道 的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟 嘟希望你能帮助他完成这样的一个选择路

8、径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。 不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。,题目模型简述,定义： 一条路径的关键边为其中费用最大的边； 一条路径的花费为其关键边的花费； 两点之间的最短路为所有连接两点的路径中花费最小的一条； 给定带权无向图G及在G上的Q个操作形如： 拆除无向边(u, v)； 询问u、v之间的最短路花费；,水管局长,你需要写一个程序完成给出的操作 数据范围： 结点数 N 1000； 边数 M 100000； 操作数 Q 1

9、00000； 删边操作 D 5000；,水管局长,周戈林同学在2006年冬令营中已经讨论过相关的问题，并提出了解决的类普里姆算法 类普里姆算法解决一次询问需要O(N2)的时间 注意到询问数可能达到105，类普里姆算法不能解决本题，为什么时间复杂度如此之高呢？,水管局长,分析一下本题时间复杂度瓶颈所在： 边数过多； 完成询问的复杂度过高； 我们将在后文逐个把这些问题解决,引入最小生成森林,引理一： 任意询问可以在G的最小生成森林中找到最优解 证明： 记(P)表示路径P中不在T中的边数 若(P) = 0，则P在T上； 若(P) 0，则存在一条边(u, v)P T,引入最小生成森林,引理一： 任意询

10、问可以在G的最小生成森林中找到最优解 证明（续）： 考察这条边(u, v)：,引入最小生成森林,引理一： 任意询问可以在G的最小生成森林中找到最优解 证明（续）： 考察这条边(u, v)： 根据最小生成森林的性质，存在一 条只有树边构成的路径P0连接u、v 两点，并且P0的花费不大于(u, v)的 花费,引入最小生成森林,引理一： 任意询问可以在G的最小生成森林中找到最优解 证明（续）： 考察这条边(u, v)： 根据最小生成森林的性质，存在一 条只有树边构成的路径P0连接u、v 两点，并且P0的花费不大于(u, v)的 花费 将P中(u, v)替换为路径P0，P的总花 费不增且(P) 减小,

11、引入最小生成森林,引理一： 任意询问可以在G的最小生成森林中找到最优解 证明（续）： 由于(P) 0，所以可以在有限次替换后将P变成一条T中的路径 这就证明了该引理,引入最小生成森林,引理一： 任意询问可以在G的最小生成森林中找到最优解 根据引理，我们只需要保存所有树边即可，这样边数下降到O(N)级别，第一个问题被解决。,完成询问,我们来考虑第二个问题 注意到最小生成森林中任意两点之间的路径是唯一的。我们可以采用DFS找出该路径中的关键边，时间消耗为O(N) 考虑到N = 1000、Q = 105，这样的时间复杂度仍然不能很好解决本题,深入思考,询问树上两点之间路径上的最大边，这种问题可以使用

12、动态树等工具实现，但是都过于复杂。 为了找出一个简单、实用的算法，我们需要仔细的研究最小生成森林的性质 Kruskal算法是建立最小生成森林中为我们所熟知的算法，以下我们将模拟一次Kruskal算法的执行,1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,我们使用Kruskal算法生成上图的最小生成森林，将所有边按照权值从小到大加入,1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(1, 2)为树边 注意到Query(1, 2)的关键边为(1, 2),1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(1, 3)为树边 注意到Query(1|2, 3

13、)的关键边为(1, 3),1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(4, 6)为树边 注意到Query(4, 6)的关键边为(4, 6),1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(5, 6)为树边 注意到Query(4|6, 5)的关键边为(5, 6),1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(2, 3) 注意到已存在路径(2, 1) (1, 3)，所以(2, 3)非树边,1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,加入边(3, 4)为树边 注意到Query(1|2|3,4|5|6)的关键边为(3,

14、4),1,2,3,4,5,6,1,5,2,6,7,3,4,1,0,此时，我们已经的到了最小生成森林T 更重要的是，我们也已经得到了所有询问的回答！,重要引理的发现,对Kruskal过程仔细思考，我们得出关键： 引理二： 任意两点u、v间最短路径的关键边，为执行Kruskal算法中第一次将此两点连通的树边！,Kruskal生成顺序森林,如何适当的应用引理二呢？所有的树边和结点需要被有机的结合起来，这里我们使用Kruskal生成顺序森林（简称顺序森林） 仍然考虑下图：,Kruskal生成顺序森林,顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点i,Kruskal生成顺序

15、森林,顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点i,V,1,V,2,V,3,V,4,V,5,V,6,Kruskal生成顺序森林,树边Ei被加入时，该边所连接的两个连通块在顺序森林中必然是两棵树,V,1,V,2,V,3,V,4,V,5,V,6,Kruskal生成顺序森林,建立顺序森林结点与Ei相对应，其左右孩子分别为两个连通块对应树的根结点,V,1,V,2,V,3,V,4,V,5,V,6,Kruskal生成顺序森林,我们模拟将所有的树边依次加入：,V,1,V,2,V,3,V,4,V,5,V,6,Kruskal生成顺序森林,添加树边(1, 2)，将原图结点1、2合并为一个连通块；我们建立顺序森林结点E1，两个儿子为V1、V2,V,1,V,2,V,3,V,4,V,5,V,6,E,1,Kruskal生成顺