《RMQ与LCA问题》宣讲培训.ppt

引入最小生成森林 引理一： 任意询问可以在G的最小生成森林中找到最优解 证明（续）： 考察这条边(u, v)： 根据最小生成森林的性质，存在一 条只有树边构成的路径P0连接u、v 两点，并且P0的花费不大于(u, v)的 花费 将P中(u, v)替换为路径P0，P的总花 费不增且Φ(P) 减小 引入最小生成森林 引理一： 任意询问可以在G的最小生成森林中找到最优解 证明（续）： 由于Φ(P) ≥ 0，所以可以在有限次替换后将P变成一条T中的路径 这就证明了该引理 引入最小生成森林 引理一： 任意询问可以在G的最小生成森林中找到最优解 根据引理，我们只需要保存所有树边即可，这样边数下降到O(N)级别，第一个问题被解决。 完成询问 我们来考虑第二个问题 注意到最小生成森林中任意两点之间的路径是唯一的。我们可以采用DFS找出该路径中的关键边，时间消耗为O(N) 考虑到N = 1000、Q = 105，这样的时间复杂度仍然不能很好解决本题 深入思考 询问树上两点之间路径上的最大边，这种问题可以使用动态树等工具实现，但是都过于复杂。 为了找出一个简单、实用的算法，我们需要仔细的研究最小生成森林的性质 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)的关键边为(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, 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生成顺序森林 顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点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生成顺序森林 添加树边(1, 3)，将原图结点1、2、3合并为一个连通块；我们建立顺序森林结点E2，两个儿子为E1、V3 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 Kruskal生成顺序森林 类似的添加树边(4, 6)时，建立顺序森林结点E3，两儿子为V4、V6 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E 3 Kruskal生成顺序森林 添加树边(5, 6)时，建立顺序森林结点E4，两儿子为V5、E3 V 1 V 2 V 3 V 4 V 5 V 6 E 1 E 2 E