尧图网站建设  / O(log N) / O(1) 三档查询复杂度与 cp-algorithms 源码剖析)
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载给定一棵根确定的树面对大量形如(v1, v2)的查询需要在极短的时间内回答两个节点的最低公共祖先Lowest Common AncestorLCA——即同时位于从根到v1与从根到v2两条路径上、且离根最远层次最深的那个顶点。本篇文章以 cp-algorithms 仓库中的 lca.md 文档为核心完整讲解「欧拉游走Euler Tour→ 区间最值 RMQ」这一经典降维思路并给出三种查询复杂度可选的预处理方案O(√N)、O(log N)、O(1)同时结合仓库内的测试代码与代码块抽取脚本剖析该结构在真实工程中的调用链与验证方式。读完你将掌握如何用一次 DFS 构造欧拉序列与first/height数组、如何把 LCA 查询等价转化为 RMQ 查询以及用 Sqrt Decomposition、Segment Tree、Sparse Table 三种数据结构承载 RMQ 的取舍。问题定义与基本性质给定一棵树G与若干形如(v1, v2)的查询。所求顶点v满足v同时位于从根到v1的路径上、以及从根到v2的路径上即v是v1与v2的公共祖先在所有公共祖先中v距离根最远即它是最「低」最深的那一个。由定义可直接推出两条被反复使用的性质LCA(v1, v2)必然位于v1到v2的最短路径上如果v1本身就是v2的祖先那么v1就是它们的最低公共祖先反之亦然。这两条性质是整个欧拉游走算法正确性的基石后续我们会看到在欧拉序列中区间内高度最小的顶点恰好就是 LCA而上述性质保证了「沿最短路 子树穿插」的遍历顺序不会漏掉或错认这个最小高度顶点。相关阅读同一仓库中 lca_binary_lifting.md 记录了另一种 $O(N \log N)$ 预处理、$O(\log N)$ 查询的倍增跳表方案本文则聚焦「欧拉游走 RMQ」这一与数据结构结合更紧密的路线。预处理一次 DFS 构造三份核心数据在回答任何查询之前需要对树进行预处理preprocessing。预处理只需要一次从根出发的 深度优先搜索 DFS并在此过程中维护三份数据结构欧拉序列euler从根开始 DFS每当「第一次访问到一个顶点」以及「从它的某个子树的 DFS 返回」时都把这个顶点追加到euler列表末尾。这样的遍历顺序也叫树的欧拉游走Euler tour。容易看出每个顶点首次出现被记一次每次从子树回溯又被记一次因此整个序列的长度是O(N)量级具体实现中常预分配2N空间。首次出现位置first[0..N-1]对每个顶点i记录它在euler中第一次出现的下标满足euler[first[i]] i。深度数组height[0..N-1]记录每个顶点到根的距离深度。DFS 进入儿子时深度加一回溯时恢复即可在遍历过程中顺带求出。需要强调的是欧拉序列不是简单地按访问顺序排列而是「进栈/出栈各记录一次」正是这种记录方式使得「从v1首次出现到v2首次出现之间的连续子段」恰好覆盖了从v1到v2的最短路径同时把路径沿途各子树的所有顶点也带了进来——而后者在后续推理中恰好可以被高度淘汰掉。核心思想LCA 查询退化为区间最小值 RMQ有了三份数据后如何回答查询(v1, v2)观察欧拉序列中从first[v1]到first[v2]这一段被访问过的顶点这段序列本质上沿着v1 → v2的最短路径前进但额外穿插访问了路径沿途所有子树的顶点关键洞察是这些额外插入的子树顶点在树中的位置都低于LCA因而其height都大于LCA 的height而真正位于最短路径上的顶点中LCA 是高度最小的那一个。因此结论是LCA(v1, v2) 欧拉序列中下标区间[first[v1], first[v2]]内height值最小的那个顶点。于是LCA 问题被完全等价地归约成了 RMQRange Minimum Query区间最小值查询问题——只需要在上述下标区间里找出高度最小的顶点即可。一旦完成这个转化就有一整个数据结构的工具箱可以拿来用RMQ 承载结构预处理时间单次查询时间说明朴素扫描$O(N)$$O(N)$不可取Sqrt Decomposition$O(N)$$O(\sqrt{N})$分块思想代码简单Segment Tree$O(N)$$O(\log N)$支持动态更新通用性强Sparse Table$O(N \log N)$$O(1)$仅适用静态数组但查询常数最小一个具体例子文档给出了如下示例树及其欧拉序列顶点序列与对应高度逐项对齐$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} 1 2 5 2 6 2 1 3 1 4 7 4 1 \ \hline \text{Heights:} 1 2 3 2 3 2 1 2 1 2 3 2 1 \ \hline \end{array}$$若要查询LCA(6, 4)从顶点 6 的首次出现到顶点 4 的首次出现访问的顶点序列为[6, 2, 1, 3, 1, 4]其高度分别为[3, 2, 1, 2, 1, 2]。其中顶点 1 的高度最小高度为 1因此LCA(6, 4) 1与上图直观一致。小结回答一次查询只需在euler数组的[first[v1], first[v2]]区间内找「高度最小的顶点」。这也是本文标题中「LCA 归约到 RMQ」的真正含义。三种 RMQ 承载方案与复杂度取舍原文档明确给出了三种可行的组合这里逐一展开说明其适用场景方案一Sqrt Decomposition查询 $O(\sqrt{N})$、预处理 $O(N)$使用 Sqrt Decomposition 把euler序列按 $\lceil \sqrt{m} \rceil$m为欧拉序列长度分块每块预先记录块内高度最小的顶点及其下标。查询时对区间两端不完整的「边角」块直接暴力扫描对中间完整覆盖的块直接取预计算的块内最小值顶点并比较合并。由于边角长度与块数都受限于 $\lceil \sqrt{m} \rceil$单次查询为 $O(\sqrt{N})$而分块预计算只需一次线性扫描预处理为 $O(N)$。这种方案代码量极小、无递归开销适合查询量不大或希望零递归深度的场景。方案二Segment Tree查询 $O(\log N)$、预处理 $O(N)$使用 Segment Tree 对euler序列建立区间最小值树查询通过标准的树节点区间分解在 $O(\log N)$ 内完成预处理只需自底向上合并总代价 $O(N)$。这也是本文核心实现选用的方案详见下文代码剖析。线段树的额外优势在于即使后续引入了针对height或euler的更新操作也能在 $O(\log N)$ 内维护。方案三Sparse Table查询 $O(1)$、预处理 $O(N \log N)$由于 LCA 场景下euler与height在预处理后几乎永远不会被修改静态数组此时 Sparse Table 是更优的选择它把查询复杂度压到理论下限 $O(1)$代价是构建时 $O(N \log N)$ 的时间与空间。Sparse Table 的核心是倍增思想——预计算所有长度为 2 的幂的区间最小值查询时用两个可重叠的 2 的幂区间覆盖目标区间。对height这种「可重叠幂区间合并」的 RMQ最小值满足幂等性两段重叠合并不影响正确性因此 $O(1)$ 查询完全可行。三种方案并非互斥如果目标是极致的查询速度且树是静态的选 Sparse Table如果查询量中等或希望模板与线段树体系共用选 Segment Tree如果追求最简实现或数据规模导致空间紧张选 Sqrt Decomposition。实现剖析基于 Segment Tree 的 LCA 结构文档给出了使用 Segment Tree 的完整 C 实现。该代码块在仓库中被标记为{.cpp filelca}测试系统会据此抽取为独立头文件详见下文「仓库中的测试验证」。逐段解读如下struct LCA { vectorint height, euler, first, segtree; vectorbool visited; int n; LCA(vectorvectorint adj, int root 0) { n adj.size(); height.resize(n); first.resize(n); euler.reserve(n * 2); visited.assign(n, false); dfs(adj, root); int m euler.size(); segtree.resize(m * 4); build(1, 0, m - 1); } void dfs(vectorvectorint adj, int node, int h 0) { visited[node] true; height[node] h; first[node] euler.size(); euler.push_back(node); for (auto to : adj[node]) { if (!visited[to]) { dfs(adj, to, h 1); euler.push_back(node); } } } void build(int node, int b, int e) { if (b e) { segtree[node] euler[b]; } else { int mid (b e) / 2; build(node 1, b, mid); build(node 1 | 1, mid 1, e); int l segtree[node 1], r segtree[node 1 | 1]; segtree[node] (height[l] height[r]) ? l : r; } } int query(int node, int b, int e, int L, int R) { if (b R || e L) return -1; if (b L e R) return segtree[node]; int mid (b e) 1; int left query(node 1, b, mid, L, R); int right query(node 1 | 1, mid 1, e, L, R); if (left -1) return right; if (right -1) return left; return height[left] height[right] ? left : right; } int lca(int u, int v) { int left first[u], right first[v]; if (left right) swap(left, right); return query(1, 0, euler.size() - 1, left, right); } };构造过程构造函数n取邻接表大小height、first依n初始化euler.reserve(n * 2)按最坏情况预分配2N容量——每个顶点「首次进入」一次、每个儿子子树返回时各记录一次总长度不超过2N - 1dfs(adj, root)从根默认root 0即 0 号顶点出发完成欧拉游走线段树按euler.size()的 4 倍开数组segtree.resize(m * 4)标准线段树最坏约4n顶点随后自根递归build。DFS 与欧拉序列的生成dfs递归参数中的h即当前深度默认为 0进入顶点即标记visited写入height[node] hfirst[node] euler.size()记录当前顶点在欧拉序列中的首次出现位置追加前的下标随后euler.push_back(node)遍历邻接表对每个未访问的邻居递归进入深度h 1返回后把node再次压入euler——这一「回溯压栈」正是欧拉游走区别于普通 DFS 序的关键也是后续区间正确覆盖最短路径的保证。注意euler中存储的是顶点编号而高度的比较在build/query中通过height[顶点]间接完成实现了「按值比较、存回顶点」的经典模式。线段树构建以「高度最小」作为合并规则build(node, b, e)处理下标区间[b, e]叶子节点b e直接保存euler[b]内部节点递归构建左右子树后取左右孩子代表的顶点中高度较小者作为当前节点的值segtree[node] (height[l] height[r]) ? l : r。也就是说这棵线段树上的每个节点都保存「其覆盖区间内高度最小的顶点编号」。构建总调用O(m)次合并每次合并为常数时间整体预处理 $O(N)$。区间查询标准的线段树分解query(node, b, e, L, R)在区间[L, R]内找高度最小的顶点完全不相交b R || e L返回哨兵值-1完全被包含b L e R直接返回节点预存值否则二分递归左右孩子然后合并两个部分结果任何一侧返回-1时取另一侧两侧都有结果时比较height取小者。由于查询区间是静态的递归路径每层至多触及少量节点单次查询为 $O(\log N)$。对外接口lca(u, v)先取两个顶点的首次出现下标left first[u]、right first[v]若left right则交换保证区间合法对[left, right]执行一次 RMQ 查询并返回顶点编号。整个对外接口只有一次线段树查询语义清晰LCA(u, v) RMQ_{height}(euler[first[u] .. first[v]])。仓库中的测试验证从文档代码块到可运行测试cp-algorithms 仓库为这段实现提供了完整的自动化验证链展示了「文档中的代码块 → 抽取为头文件 → 编译运行断言」的工程闭环代码块抽取test/extract_snippets.py 会扫描src/下所有 Markdown用正则^\{.cpp file(\S)\}$匹配带file标记的代码块并把块内容写成同名.h文件。lca.md中的{.cpp filelca}代码块因此会被抽取为lca.h供测试程序#include lca.h使用。测试用例test/test_lca.cpp 构造了一棵 7 节点的树adj[0] {1, 2, 3}、adj[2] {4, 5, 6}即根 0 有三个孩子、节点 2 有 4/5/6 三个孩子然后对LCA结构断言#include cassert #include vector using namespace std; #include lca.h int main() { vectorvectorint adj(7); adj[0] {1, 2, 3}; adj[2] {4, 5, 6}; LCA lca(adj, 0); assert(lca.lca(4, 6) 2); // 4 与 6 的 LCA 是 2 assert(lca.lca(1, 6) 0); // 1 与 6 的 LCA 是根 0 assert(lca.lca(0, 3) 0); // 根自身参与的查询 assert(lca.lca(2, 2) 2); // u v 时 LCA 即其自身 return 0; }这些断言恰好覆盖了本文算法的关键正确性情形兄弟子树查询4 与 6、跨分支查询1 与 6、根参与查询、以及u v的退化情形此时first[u] first[v]区间退化为单元素返回u自身。 3.编译与运行test/test.sh 依次对每个*.cpp用g -stdc17 -fsanitizeundefined -fno-sanitize-recover编译并执行全部断言通过则输出绿色Passed任一测试失败则汇总报错并以非零退出码结束。仓库中的 test/clean.sh 负责清理抽取产生的*.h临时文件。从源码结构可以推断这套「Markdown 代码块 ↔ 头文件 ↔ 测试驱动」的流水线是仓库中所有算法文章共用的验证机制文档即源码、源码即可测既保证了文章示例不漂移也让读者可以随时自行复现实验。应用与延伸LCA 是树结构问题的「基础设施」在仓库中还有大量直接相关的延伸阅读倍增法 LCAlca_binary_lifting.md 提供 $O(N \log N)$ 预处理、$O(\log N)$ 查询的另一种主流实现不依赖 RMQ 数据结构常与本文方案互补离线 Tarjan / RMQ 线性实现仓库中的 lca_tarjan.mdTarjan 离线 LCA与 lca_farachcoltonbender.mdFarach–Colton 与 Bender 的 ±1 RMQ 线性算法给出了更多复杂度档次DFS 基础depth-first-search.md 明确把「求两个顶点的 LCA」列为 DFS 的典型应用之一其 entry/exit 时间戳技巧与本文的first/height数组思想同源RMQ 数据结构segment_tree.md、sparse-table.md、sqrt_decomposition.md 分别承载本文的三种查询方案可作为各自的完整教程树上距离计算有了 LCA树上任意两点u、v的距离即可由height[u] height[v] - 2 * height[LCA(u, v)]在 $O(1)$配合 Sparse Table或 $O(\log N)$ 内求得这是树形网络、最近点对、路径查询等一大类题目的公共前置步骤。原文档末尾还给出了一系列经典练习题目SPOJ LCA、SPOJ DISQUERY、TIMUS 1471 Distance in the Tree、Codeforces 472/D Design Tutorial、Codechef TALCA、UVA 12655 Trucks 等覆盖了从裸 LCA 到「LCA 结合边权距离、树上最小/最大边、路径计数」的各种进阶形态非常适合用来巩固本文的欧拉游走 RMQ 模板。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐深度解析 xiaomusic 项目网络配置架构XIAOMUSIC_HOSTNAME 配置的设计哲学与最佳实践深度解析 xiaomusic 项目网络配置架构XIAOMUSIC_HOSTNAME 配置的设计哲学与最佳实践 在构建基于小爱音箱的音乐播放系统时网络配置的正后端智能硬件音视频免费解决凌晨三点告警风暴开源告警管理工具 Keep 快速上手指南免费解决凌晨三点告警风暴开源告警管理工具 Keep 快速上手指南 凌晨三点手机突然震个不停值班群被 Prometheus、Datadog 的通知刷屏而你文档教程知识库cp-algorithms 扫描线法查找相交线段对从 O(n²) 到 O(n log n) 的完整实现与原理剖析cp algorithms 扫描线法查找相交线段对从 O n² 到 O n log n 的完整实现与原理剖析 给定平面上的 $n$ 条线段需要判断其中是否存文档教程知识库上一篇革命性AI代理框架youtu-agent10分钟快速上手开源模型驱动的智能助手下一篇阿里通义千问推出Qwen3-4B-Thinking-2507-FP8轻量化模型实现推理能力质的飞跃创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 树的最深公共祖先 LCA（欧拉游走 + RMQ 解法）：O(√N) / O(log N) / O(1) 三档查询复杂度与 cp-algorithms 源码剖析
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载给定一棵根确定的树面对大量形如(v1, v2)的查询需要在极短的时间内回答两个节点的最低公共祖先Lowest Common AncestorLCA——即同时位于从根到v1与从根到v2两条路径上、且离根最远层次最深的那个顶点。本篇文章以 cp-algorithms 仓库中的 lca.md 文档为核心完整讲解「欧拉游走Euler Tour→ 区间最值 RMQ」这一经典降维思路并给出三种查询复杂度可选的预处理方案O(√N)、O(log N)、O(1)同时结合仓库内的测试代码与代码块抽取脚本剖析该结构在真实工程中的调用链与验证方式。读完你将掌握如何用一次 DFS 构造欧拉序列与first/height数组、如何把 LCA 查询等价转化为 RMQ 查询以及用 Sqrt Decomposition、Segment Tree、Sparse Table 三种数据结构承载 RMQ 的取舍。问题定义与基本性质给定一棵树G与若干形如(v1, v2)的查询。所求顶点v满足v同时位于从根到v1的路径上、以及从根到v2的路径上即v是v1与v2的公共祖先在所有公共祖先中v距离根最远即它是最「低」最深的那一个。由定义可直接推出两条被反复使用的性质LCA(v1, v2)必然位于v1到v2的最短路径上如果v1本身就是v2的祖先那么v1就是它们的最低公共祖先反之亦然。这两条性质是整个欧拉游走算法正确性的基石后续我们会看到在欧拉序列中区间内高度最小的顶点恰好就是 LCA而上述性质保证了「沿最短路 子树穿插」的遍历顺序不会漏掉或错认这个最小高度顶点。相关阅读同一仓库中 lca_binary_lifting.md 记录了另一种 $O(N \log N)$ 预处理、$O(\log N)$ 查询的倍增跳表方案本文则聚焦「欧拉游走 RMQ」这一与数据结构结合更紧密的路线。预处理一次 DFS 构造三份核心数据在回答任何查询之前需要对树进行预处理preprocessing。预处理只需要一次从根出发的 深度优先搜索 DFS并在此过程中维护三份数据结构欧拉序列euler从根开始 DFS每当「第一次访问到一个顶点」以及「从它的某个子树的 DFS 返回」时都把这个顶点追加到euler列表末尾。这样的遍历顺序也叫树的欧拉游走Euler tour。容易看出每个顶点首次出现被记一次每次从子树回溯又被记一次因此整个序列的长度是O(N)量级具体实现中常预分配2N空间。首次出现位置first[0..N-1]对每个顶点i记录它在euler中第一次出现的下标满足euler[first[i]] i。深度数组height[0..N-1]记录每个顶点到根的距离深度。DFS 进入儿子时深度加一回溯时恢复即可在遍历过程中顺带求出。需要强调的是欧拉序列不是简单地按访问顺序排列而是「进栈/出栈各记录一次」正是这种记录方式使得「从v1首次出现到v2首次出现之间的连续子段」恰好覆盖了从v1到v2的最短路径同时把路径沿途各子树的所有顶点也带了进来——而后者在后续推理中恰好可以被高度淘汰掉。核心思想LCA 查询退化为区间最小值 RMQ有了三份数据后如何回答查询(v1, v2)观察欧拉序列中从first[v1]到first[v2]这一段被访问过的顶点这段序列本质上沿着v1 → v2的最短路径前进但额外穿插访问了路径沿途所有子树的顶点关键洞察是这些额外插入的子树顶点在树中的位置都低于LCA因而其height都大于LCA 的height而真正位于最短路径上的顶点中LCA 是高度最小的那一个。因此结论是LCA(v1, v2) 欧拉序列中下标区间[first[v1], first[v2]]内height值最小的那个顶点。于是LCA 问题被完全等价地归约成了 RMQRange Minimum Query区间最小值查询问题——只需要在上述下标区间里找出高度最小的顶点即可。一旦完成这个转化就有一整个数据结构的工具箱可以拿来用RMQ 承载结构预处理时间单次查询时间说明朴素扫描$O(N)$$O(N)$不可取Sqrt Decomposition$O(N)$$O(\sqrt{N})$分块思想代码简单Segment Tree$O(N)$$O(\log N)$支持动态更新通用性强Sparse Table$O(N \log N)$$O(1)$仅适用静态数组但查询常数最小一个具体例子文档给出了如下示例树及其欧拉序列顶点序列与对应高度逐项对齐$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} 1 2 5 2 6 2 1 3 1 4 7 4 1 \ \hline \text{Heights:} 1 2 3 2 3 2 1 2 1 2 3 2 1 \ \hline \end{array}$$若要查询LCA(6, 4)从顶点 6 的首次出现到顶点 4 的首次出现访问的顶点序列为[6, 2, 1, 3, 1, 4]其高度分别为[3, 2, 1, 2, 1, 2]。其中顶点 1 的高度最小高度为 1因此LCA(6, 4) 1与上图直观一致。小结回答一次查询只需在euler数组的[first[v1], first[v2]]区间内找「高度最小的顶点」。这也是本文标题中「LCA 归约到 RMQ」的真正含义。三种 RMQ 承载方案与复杂度取舍原文档明确给出了三种可行的组合这里逐一展开说明其适用场景方案一Sqrt Decomposition查询 $O(\sqrt{N})$、预处理 $O(N)$使用 Sqrt Decomposition 把euler序列按 $\lceil \sqrt{m} \rceil$m为欧拉序列长度分块每块预先记录块内高度最小的顶点及其下标。查询时对区间两端不完整的「边角」块直接暴力扫描对中间完整覆盖的块直接取预计算的块内最小值顶点并比较合并。由于边角长度与块数都受限于 $\lceil \sqrt{m} \rceil$单次查询为 $O(\sqrt{N})$而分块预计算只需一次线性扫描预处理为 $O(N)$。这种方案代码量极小、无递归开销适合查询量不大或希望零递归深度的场景。方案二Segment Tree查询 $O(\log N)$、预处理 $O(N)$使用 Segment Tree 对euler序列建立区间最小值树查询通过标准的树节点区间分解在 $O(\log N)$ 内完成预处理只需自底向上合并总代价 $O(N)$。这也是本文核心实现选用的方案详见下文代码剖析。线段树的额外优势在于即使后续引入了针对height或euler的更新操作也能在 $O(\log N)$ 内维护。方案三Sparse Table查询 $O(1)$、预处理 $O(N \log N)$由于 LCA 场景下euler与height在预处理后几乎永远不会被修改静态数组此时 Sparse Table 是更优的选择它把查询复杂度压到理论下限 $O(1)$代价是构建时 $O(N \log N)$ 的时间与空间。Sparse Table 的核心是倍增思想——预计算所有长度为 2 的幂的区间最小值查询时用两个可重叠的 2 的幂区间覆盖目标区间。对height这种「可重叠幂区间合并」的 RMQ最小值满足幂等性两段重叠合并不影响正确性因此 $O(1)$ 查询完全可行。三种方案并非互斥如果目标是极致的查询速度且树是静态的选 Sparse Table如果查询量中等或希望模板与线段树体系共用选 Segment Tree如果追求最简实现或数据规模导致空间紧张选 Sqrt Decomposition。实现剖析基于 Segment Tree 的 LCA 结构文档给出了使用 Segment Tree 的完整 C 实现。该代码块在仓库中被标记为{.cpp filelca}测试系统会据此抽取为独立头文件详见下文「仓库中的测试验证」。逐段解读如下struct LCA { vectorint height, euler, first, segtree; vectorbool visited; int n; LCA(vectorvectorint adj, int root 0) { n adj.size(); height.resize(n); first.resize(n); euler.reserve(n * 2); visited.assign(n, false); dfs(adj, root); int m euler.size(); segtree.resize(m * 4); build(1, 0, m - 1); } void dfs(vectorvectorint adj, int node, int h 0) { visited[node] true; height[node] h; first[node] euler.size(); euler.push_back(node); for (auto to : adj[node]) { if (!visited[to]) { dfs(adj, to, h 1); euler.push_back(node); } } } void build(int node, int b, int e) { if (b e) { segtree[node] euler[b]; } else { int mid (b e) / 2; build(node 1, b, mid); build(node 1 | 1, mid 1, e); int l segtree[node 1], r segtree[node 1 | 1]; segtree[node] (height[l] height[r]) ? l : r; } } int query(int node, int b, int e, int L, int R) { if (b R || e L) return -1; if (b L e R) return segtree[node]; int mid (b e) 1; int left query(node 1, b, mid, L, R); int right query(node 1 | 1, mid 1, e, L, R); if (left -1) return right; if (right -1) return left; return height[left] height[right] ? left : right; } int lca(int u, int v) { int left first[u], right first[v]; if (left right) swap(left, right); return query(1, 0, euler.size() - 1, left, right); } };构造过程构造函数n取邻接表大小height、first依n初始化euler.reserve(n * 2)按最坏情况预分配2N容量——每个顶点「首次进入」一次、每个儿子子树返回时各记录一次总长度不超过2N - 1dfs(adj, root)从根默认root 0即 0 号顶点出发完成欧拉游走线段树按euler.size()的 4 倍开数组segtree.resize(m * 4)标准线段树最坏约4n顶点随后自根递归build。DFS 与欧拉序列的生成dfs递归参数中的h即当前深度默认为 0进入顶点即标记visited写入height[node] hfirst[node] euler.size()记录当前顶点在欧拉序列中的首次出现位置追加前的下标随后euler.push_back(node)遍历邻接表对每个未访问的邻居递归进入深度h 1返回后把node再次压入euler——这一「回溯压栈」正是欧拉游走区别于普通 DFS 序的关键也是后续区间正确覆盖最短路径的保证。注意euler中存储的是顶点编号而高度的比较在build/query中通过height[顶点]间接完成实现了「按值比较、存回顶点」的经典模式。线段树构建以「高度最小」作为合并规则build(node, b, e)处理下标区间[b, e]叶子节点b e直接保存euler[b]内部节点递归构建左右子树后取左右孩子代表的顶点中高度较小者作为当前节点的值segtree[node] (height[l] height[r]) ? l : r。也就是说这棵线段树上的每个节点都保存「其覆盖区间内高度最小的顶点编号」。构建总调用O(m)次合并每次合并为常数时间整体预处理 $O(N)$。区间查询标准的线段树分解query(node, b, e, L, R)在区间[L, R]内找高度最小的顶点完全不相交b R || e L返回哨兵值-1完全被包含b L e R直接返回节点预存值否则二分递归左右孩子然后合并两个部分结果任何一侧返回-1时取另一侧两侧都有结果时比较height取小者。由于查询区间是静态的递归路径每层至多触及少量节点单次查询为 $O(\log N)$。对外接口lca(u, v)先取两个顶点的首次出现下标left first[u]、right first[v]若left right则交换保证区间合法对[left, right]执行一次 RMQ 查询并返回顶点编号。整个对外接口只有一次线段树查询语义清晰LCA(u, v) RMQ_{height}(euler[first[u] .. first[v]])。仓库中的测试验证从文档代码块到可运行测试cp-algorithms 仓库为这段实现提供了完整的自动化验证链展示了「文档中的代码块 → 抽取为头文件 → 编译运行断言」的工程闭环代码块抽取test/extract_snippets.py 会扫描src/下所有 Markdown用正则^\{.cpp file(\S)\}$匹配带file标记的代码块并把块内容写成同名.h文件。lca.md中的{.cpp filelca}代码块因此会被抽取为lca.h供测试程序#include lca.h使用。测试用例test/test_lca.cpp 构造了一棵 7 节点的树adj[0] {1, 2, 3}、adj[2] {4, 5, 6}即根 0 有三个孩子、节点 2 有 4/5/6 三个孩子然后对LCA结构断言#include cassert #include vector using namespace std; #include lca.h int main() { vectorvectorint adj(7); adj[0] {1, 2, 3}; adj[2] {4, 5, 6}; LCA lca(adj, 0); assert(lca.lca(4, 6) 2); // 4 与 6 的 LCA 是 2 assert(lca.lca(1, 6) 0); // 1 与 6 的 LCA 是根 0 assert(lca.lca(0, 3) 0); // 根自身参与的查询 assert(lca.lca(2, 2) 2); // u v 时 LCA 即其自身 return 0; }这些断言恰好覆盖了本文算法的关键正确性情形兄弟子树查询4 与 6、跨分支查询1 与 6、根参与查询、以及u v的退化情形此时first[u] first[v]区间退化为单元素返回u自身。 3.编译与运行test/test.sh 依次对每个*.cpp用g -stdc17 -fsanitizeundefined -fno-sanitize-recover编译并执行全部断言通过则输出绿色Passed任一测试失败则汇总报错并以非零退出码结束。仓库中的 test/clean.sh 负责清理抽取产生的*.h临时文件。从源码结构可以推断这套「Markdown 代码块 ↔ 头文件 ↔ 测试驱动」的流水线是仓库中所有算法文章共用的验证机制文档即源码、源码即可测既保证了文章示例不漂移也让读者可以随时自行复现实验。应用与延伸LCA 是树结构问题的「基础设施」在仓库中还有大量直接相关的延伸阅读倍增法 LCAlca_binary_lifting.md 提供 $O(N \log N)$ 预处理、$O(\log N)$ 查询的另一种主流实现不依赖 RMQ 数据结构常与本文方案互补离线 Tarjan / RMQ 线性实现仓库中的 lca_tarjan.mdTarjan 离线 LCA与 lca_farachcoltonbender.mdFarach–Colton 与 Bender 的 ±1 RMQ 线性算法给出了更多复杂度档次DFS 基础depth-first-search.md 明确把「求两个顶点的 LCA」列为 DFS 的典型应用之一其 entry/exit 时间戳技巧与本文的first/height数组思想同源RMQ 数据结构segment_tree.md、sparse-table.md、sqrt_decomposition.md 分别承载本文的三种查询方案可作为各自的完整教程树上距离计算有了 LCA树上任意两点u、v的距离即可由height[u] height[v] - 2 * height[LCA(u, v)]在 $O(1)$配合 Sparse Table或 $O(\log N)$ 内求得这是树形网络、最近点对、路径查询等一大类题目的公共前置步骤。原文档末尾还给出了一系列经典练习题目SPOJ LCA、SPOJ DISQUERY、TIMUS 1471 Distance in the Tree、Codeforces 472/D Design Tutorial、Codechef TALCA、UVA 12655 Trucks 等覆盖了从裸 LCA 到「LCA 结合边权距离、树上最小/最大边、路径计数」的各种进阶形态非常适合用来巩固本文的欧拉游走 RMQ 模板。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐深度解析 xiaomusic 项目网络配置架构XIAOMUSIC_HOSTNAME 配置的设计哲学与最佳实践深度解析 xiaomusic 项目网络配置架构XIAOMUSIC_HOSTNAME 配置的设计哲学与最佳实践 在构建基于小爱音箱的音乐播放系统时网络配置的正后端智能硬件音视频免费解决凌晨三点告警风暴开源告警管理工具 Keep 快速上手指南免费解决凌晨三点告警风暴开源告警管理工具 Keep 快速上手指南 凌晨三点手机突然震个不停值班群被 Prometheus、Datadog 的通知刷屏而你文档教程知识库cp-algorithms 扫描线法查找相交线段对从 O(n²) 到 O(n log n) 的完整实现与原理剖析cp algorithms 扫描线法查找相交线段对从 O n² 到 O n log n 的完整实现与原理剖析 给定平面上的 $n$ 条线段需要判断其中是否存文档教程知识库上一篇革命性AI代理框架youtu-agent10分钟快速上手开源模型驱动的智能助手下一篇阿里通义千问推出Qwen3-4B-Thinking-2507-FP8轻量化模型实现推理能力质的飞跃创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考