信息学数据结构rmqlca问题

1、RMQ&LCA问题雅礼 朱全民思考问题读入n个数：a1,a2,a3,an共有m个操作，每种操作分两类：1、修改一个值2、询问某个区间中的最小值n=100000m=100000 （m为操作次数）朴素的方法，时间复杂度为 O（nm）RMQ问题已知长度为L 的数列A ，询问区间l, r 中的最值。若询问的次数较少，可以用线性的复杂度来查询，但如果询问的次数过多且L 过大，那么复杂度就会很高。所以需要更快速的查找方法。 RMQ示例RMQ的主要算法在线算法：线段树 O(nlogn) 离线算法：ST算法（动态规划） O(nlogn)-O(1)离线算法：笛卡尔树O(n)ST算法（Sparse Table）S

2、T算法运用的主要思想是倍增思想。设fi,j表示从i开始向后数2j个元素的最小值递推方程就是 fi,j:=min(fi,j-1,fi+2j-1,j-1);边界：fi,0:=ai;设 k:=trunc(ln(j-i+1)/ln(2) RMQ(i,j):=min(fi,k,fj-2k+1,k);RMQ代码 Read(n, q); for i := 1 to n do Read(di, 0); for j := 1 to Trunc(Ln(n) / Ln(2) do for i := 1 to n - 1 shl j + 1 do di,j := Min(di,j-1, di+1 shl (j-1),

3、j-1); for i := 1 to q do begin Read(a, b); k := Trunc(Ln(b - a + 1) / Ln(2); rmq := Min(da, k, db - 1 shl k + 1, k); Writeln(rmq); #define Min(a, b) (a)(b)?(a):(b) int Dmin5000520; / 最小值的DP 矩阵 int num50005; / 记录区间中的数据 void Init(int N) / 计算DP 矩阵 DP 规则如上 int i, j, M; for (i=1; i=N; i+) Dmini0=numi; fo

4、r (i=1, M=1; M0; j-) Dminji=Dminji-1; if (j+(1(i-1)=N) Dminji=Min(Dminji, Dminj+(1(i-1)i-1); return; int RMQ(int l, int r) / 计算l, r 区间中的最小值 int i, j, k; k=r-l+1; / 记录区间中数字的个数 for (i=0, j=1; 2*j=k; j=1, i+); int a=Min(Dminli, Dminr-j+1i); return a; 思考怎样求一个数字矩阵中的RMQ?LCA 问题最近公共祖先( Lowest Common Ancesto

5、rs ) 对于有根树T 的两个结点u 、v ，LCA(T, u, v) 表示一个结点x ，满足x 是u 、v 的祖先且x 的深度尽可能大（即离根最远）。Tarjan离线算法1 、在并查集中建立仅包含x 结点的集合，即Fax=x; 2 、处理x 的所有孩子，处理完每个孩子后，令Fa 孩子=x ，即将孩子和x 所在集合合并； 3 、全部孩子处理完后，将x 标记为处理结束； 4 、处理所有与x 相关的询问。对于每个询问LCA(x, y) ，若y 已被标记，则记录下LCA(x, y)=Find(y) ，即y 所在集合的代表元素。LCA 与RMQ RMQ 向LCA 转化：设序列A 的长度为N 1 、设序

6、列中最小值为为Ak ，建立优先级为Ak 的根结点Tk ；2 、将A1.k-1 递归建树作为Tk 的左子树； 3 、将Ak+1.N 递归建树作为Tk 的右子树。 RMQ(A, i, j) 查询Ai.j 的最值即为LCA(T, i, j) 。 LCA 向RMQ 转化： 对有根树T 进行DFS ，将遍历到的结点按照顺序记下，得到一个长度为2*N-1 的序列，称之为T 的欧拉序列F ，每个结点在欧拉序列中出现，记录posu 为结点u 在欧拉序列中 第一次出现的位置。 LCA(T, u, v)=RMQ(B, pos(u), pos(v) 笛卡尔树(Cartesian Tree)算法这个方法的精髓在于将R

7、MQ问题转化为LCA问题。笛卡尔树的定义:对于一个数组A来说，笛卡尔树的根的编号是这个数组的最小值的所在的编号k。他的左子树就是在数组A1.k-1上的一棵笛卡尔树，右子树是一棵在数组Ak+1.n的一棵笛卡尔树。Cartesian 树的建立首先，先从A1开始建立，以后每次加一个数，就修改Cartesian数，不难发现，这个数一定在这棵树的最右边的路径上。而且一定没有右孩子（应为数组为树的中序遍历），所以，只沿着最右路径自底向上把各个节点p和Ai做比较，如果pAi，那么比较p的父亲与Ai，如果Aip的父亲，那么Ai为p的父亲的右孩子，而p则改为Ai的左孩子。因为每个节点最多进入和退出最右路径各一次

8、，所以，均摊时间复杂度为O(n)。定理：数组A的Cartesian数记为C(A)，则RMQ(A, i, j) = LCA(C(A), i, j).水管局长（原题）SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在 处理每项送水任务之前，路径上的水管都要进行一系

9、列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道 的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟 嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。题目模型简述定义：一条路径的关键边为其中费用最大的边；一条路径的花费为其关键边的花费；两

10、点之间的最短路为所有连接两点的路径中花费最小的一条；给定带权无向图G及在G上的Q个操作形如：拆除无向边(u, v)；询问u、v之间的最短路花费；水管局长你需要写一个程序完成给出的操作数据范围：结点数 N 1000；边数 M 100000；操作数 Q 100000；删边操作 D 5000；水管局长分析一下本题时间复杂度瓶颈所在：边数过多；完成询问的复杂度过高；我们将在后文逐个把这些问题解决引入最小生成森林引理一：任意询问可以在G的最小生成森林中找到最优解证明：记(P)表示路径P中不在T中的边数若(P) = 0，则P在T上；若(P) 0，则存在一条边(u, v)P T引入最小生成森林引理一：任意询

11、问可以在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) 减小引入最小生成森林引理一：任意询问可以在G的最小

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

13、的研究最小生成森林的性质Kruskal算法是建立最小生成森林中为我们所熟知的算法，以下我们将模拟一次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)为树

14、边注意到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更重要的是，我们也已经得到了所有询问的回答！重要引理的发现对Kruskal过程仔细思考，我们得出关键：引理二：任意两点u、v间最短路径的关键边，为执行Kruskal算法中第一次将此两点连通的树边！Kruskal生成顺序森林如何适当的应用引理二呢？所

15、有的树边和结点需要被有机的结合起来，这里我们使用Kruskal生成顺序森林（简称顺序森林）仍然考虑下图：Kruskal生成顺序森林顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点iKruskal生成顺序森林顺序森林的每个叶结点对应原图的一个结点，如下图所示，叶结点Vi对应原图的结点iV1V2V3V4V5V6Kruskal生成顺序森林树边Ei被加入时，该边所连接的两个连通块在顺序森林中必然是两棵树V1V2V3V4V5V6Kruskal生成顺序森林建立顺序森林结点与Ei相对应，其左右孩子分别为两个连通块对应树的根结点V1V2V3V4V5V6Kruskal生成顺序森林我们

16、模拟将所有的树边依次加入：V1V2V3V4V5V6Kruskal生成顺序森林添加树边(1, 2)，将原图结点1、2合并为一个连通块；我们建立顺序森林结点E1，两个儿子为V1、V2V1V2V3V4V5V6E1Kruskal生成顺序森林添加树边(1, 3)，将原图结点1、2、3合并为一个连通块；我们建立顺序森林结点E2，两个儿子为E1、V3V1V2V3V4V5V6E1E2Kruskal生成顺序森林类似的添加树边(4, 6)时，建立顺序森林结点E3，两儿子为V4、V6V1V2V3V4V5V6E1E2E3Kruskal生成顺序森林添加树边(5, 6)时，建立顺序森林结点E4，两儿子为V5、E3V1V2V3V4V5V6E1E2E3E4Kruskal生成顺序森林添加树边(3, 4)时，建立顺序森林结点E5，两儿子为E2、E4V1V2V3V4V5V6E1E2E3E4E5Kruskal生成顺序森林我们得到了图G的最小生成顺序森林V1V2V3V4V5V6E1E2E3E4E5引入LCA解决问题！不难发现，Query(Vi, Vj)即为顺序森林中他们的最近公共祖先！根据已有的成