《RMQ与LCA问题》.ppt

《《RMQ与LCA问题》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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称为±1RMQRMQ&LCA问题的解决在研究人员的努力下，RMQ&LCA问题已经获得了比较完善的解决方案，这里我们只列出一些常用算法的适用范围以及他们的时空复杂度：算法名称针对问题时间消耗空间消耗ST算法一般RMQ问题O(Nlog2N)Tar

2、jan算法LCA问题O(N)±1RMQ算法±1RMQ问题O(N)注：N表示问题规模，Q表示询问次数RMQ&LCA问题的解决我们以O(f(N))–O(g(N))描述一个在线算法，在O(f(N))的时间内完成预处理，在O(g(N))的时间内完成一次询问以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问题的解

3、决这些算法各自具有特点，但是针对问题过于狭窄。下文中我们将会看到，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的转化考察一个长度为N的序列A，按照如下方法将其递归建立为一棵树：设序列中最小值为Ak，建立优先级为Ak的根节点Tk；将A(1…k–1)递归建树作为Tk的左子树；将A(k+1…N)

4、递归建树作为Tk的右子树；不难发现，这棵树是一棵优先级树A=(758110)我们以A序列为例建立树TA=(758110)1将最小元素1作为根节点左右分别建树A=(758110)110右子树只有一个结点，即10A=(758110)110左子树有三个结点7、5、8A=(758110)1105左子树有三个结点7、5、8将最小元素5作为根节点左右分别建树A=(758110)110578元素5的左右子树都只有一个结点，分别是7、8A=(758110)110578这样我们便得到了树TRMQ向LCA的转化对于RMQ(A，i，j)：设序列中最小值为Ak，若k∈[i,j]，那么答

5、案为k；若k>j，那么答案为RMQ(A1..k-1，i，j)；若k

6、DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u,v)有且仅有一次，且深度是深度序列B[pos(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)有且仅有一次，且深度是深度序列B[pos(u)…pos(v)]中最小的这就证明了LCA问题可以转化成RMQ问题LCA与RMQ问题可以互相转化，并且可以在O(N)的时间内完成！RMQ&LCA算法关系

7、图一般RMQ问题±1RMQ问题LCA问题ST算法Tarjan算法±1RMQ算法O(N)O(N)III.问题的应用问题的应用RMQ&LCA问题在算法研究及信息学竞赛中都发挥着十分重要的作用，它主要是以一种经典算法及解题思想的形式出现本文主要以讨论一道例题：水管局长（2006年冬令营试题）水管局长（原题）SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径

8、上每一条水管都准备好了，