最近公共祖先 Least Common Ancestors(LCA)算法 --- 与RMQ问题的转换
2024-09-02 02:43:56
【简介】
LCA(T,u,v):在有根树T中,询问一个距离根最远的结点x,使得x同时为结点u、v的祖先。
RMQ(A,i,j):对于线性序列A中,询问区间[i,j]上的最值。见我的博客---RMQ ---- ST(Sparse Table)算法。
【LCA算法】
解决LCA问题有多种算法,一种是离线的 Tarjan算法 ,还有在线的倍增法 ,还有就是转换为RMQ问题的在线算法。
【LCA转化为RMQ】
(一)对有根树T进行DFS,将遍历到的结点按照顺序记下,我们将得到一个长度为2N – 1的序列,称之为T的欧拉序列F 。
(二)每个结点都在欧拉序列中出现,我们记录结点u在欧拉序列中第一次出现的位置为pos(u)。
根据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问题。
【RMQ转化为LCA】
简单说明下吧:考察一个长度为N的序列A,按照如下方法将其递归建立为一棵树:
1)设序列中最小值为Ak,建立优先级为Ak的根节点Tk;
2)将A(1…k–1)递归建树作为Tk的左子树;
3)将A(k+1…N)递归建树作为Tk的右子树;
不难发现,这棵树是一棵优先级树T。
对于RMQ(A,i,j):
1)设序列中最小值为Ak,若k∈[i, j],那么答案为k;
2)若k > j,那么答案为RMQ(A1..k-1,i,j);
3)若k < i,那么答案为RMQ(AK+1..N,i,j);
不难发现RMQ(A,i,j) = LCA(T,i,j)!
【例题 HDU 2586】
最新文章
- Unity Container 应用示例
- C# Susan边缘检测(Susan Edge Detection)
- noi 8462 大盗阿福
- win10使用Composer-Setup安装Composer以及使用Composer安装Yii2最新版
- The Linux Storage Stack Diagram
- python中的异常处理
- IntelliJ IDEA 注册码
- VSX规划Package文件
- zoj 3761
- HDU4349--Xiao Ming&#39;s Hope(数论)
- C++中联合体(union)的使用
- ffmpeg常用命令---转
- 一个开源的强类型客户端(.NET 中的 Open Fegin)&mdash; Rabbit Go
- Swing——鼠标(Action)
- SQL NOW() 函数
- Xcode9.2打包图片显示异常解决方案
- leetcode3
- 1021 docker搭建mysql、网络模式、grid
- 写入Csv
- python3好用的requests库