最近公共祖先¶
定义¶
最近公共祖先（LCA，Lowest Common Ancestor），顾名思义就是最近的公共祖先。
一个集合 \(S\) 的最近公共祖先 \(\text{LCA}(S)=\text{LCA}(s_1,s_2,\dots,s_k)\) 定义为：
这个集合中所有节点，其祖先的交集中，离根最远的那个。
性质¶
在数值的关系上：
- \(\text{LCA}(\{u\})=u\)；
- \(\text{LCA}(A\cup B)=\text{LCA}\{\text{LCA}(A),\text{LCA}(B)\}\)；
- \(d(u,v)=h(u)+h(v)-2\text{LCA}\{u,v\}\)。
在形态的关系上：
- \(u\) 是 \(v\) 的祖先，当且仅当 \(\text{LCA}\{u,v\}=u\)；
- 两个点的最近公共祖先一定在这两个点的最短路上。
算法¶
由于我们可以把一个集合不断拆分，最终将问题拆分为：求任意两个点 \(u,v\) 的 LCA。
朴素算法¶
设 \(c\) 表示节点 \(u,v\) 的 LCA，考虑到 \(c\) 深度一定比 \(u,v\) 都要小。
于是我们可以先把 \(u,v\) 中比较深的那一个往上跳，最终得到 \(u',v'\)。
即，从两个点一步一步往上跳，跳到同一高度后再一起跳。
优化算法¶
很多，我们在此列举：
| 算法 | 预处理复杂度 | 查询复杂度 | 特点 |
|---|---|---|---|
| 倍增 | \(\mathcal O(n\log n)\) | \(\mathcal O(\log n)\) | 跑满 \(\log\) |
| 欧拉序 | \(\mathcal O(n\log n)\) | \(\mathcal O(1)\) | 常数较大 |
| DFS 序 | \(\mathcal O(n\log n)\) | \(\mathcal O(1)\) | 常数较小 |
| 树链剖分 | \(\mathcal O(n)\) | \(\mathcal O(\log n)\) | 常数很小 |
还有一些奇妙的，例如 Tarjan、四毛子、±1 RMQ 等，暂时不写。
-
一般来说，询问量很大的时候用 DFS 序，否则用树链剖分。
-
当求 LCA 不是复杂度瓶颈的时候，可以用倍增（好写）。
我们开始详细讲解每一个。
本页面最近更新：正在加载中，更新历史。
编辑页面：在 GitHub 上编辑此页！
本页面贡献者：RainPPR。