企业官网建设流程全解析

• 文档
• 教程
• 知识库

给定一棵根确定的树，面对大量形如(v1, v2)的查询，需要在极短的时间内回答两个节点的最低公共祖先（Lowest Common Ancestor，LCA）——即同时位于从根到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距离根最远，即它是最「低」（最深）的那一个。

由定义可直接推出两条被反复使用的性质：

1. LCA(v1, v2)必然位于v1到v2的最短路径上；
2. 如果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 问题被完全等价地归约成了 RMQ（Range Minimum Query，区间最小值查询）问题——只需要在上述下标区间里找出高度最小的顶点即可。一旦完成这个转化，就有一整个数据结构的工具箱可以拿来用：

一个具体例子

文档给出了如下示例树及其欧拉序列（顶点序列与对应高度逐项对齐）：

$$\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 file=lca}，测试系统会据此抽取为独立头文件（详见下文「仓库中的测试验证」）。逐段解读如下：

struct LCA { vector<int> height, euler, first, segtree; vector<bool> visited; int n; LCA(vector<vector<int>> &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(vector<vector<int>> &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 - 1；
• dfs(adj, root)：从根（默认root = 0，即 0 号顶点）出发完成欧拉游走；
• 线段树按euler.size()的 4 倍开数组（segtree.resize(m * 4)，标准线段树最坏约4n顶点），随后自根递归build。

DFS 与欧拉序列的生成

dfs递归参数中的h即当前深度，默认为 0：

• 进入顶点即标记visited，写入height[node] = h；
• first[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 仓库为这段实现提供了完整的自动化验证链，展示了「文档中的代码块 → 抽取为头文件 → 编译运行断言」的工程闭环：

1. 代码块抽取：test/extract_snippets.py 会扫描src/下所有 Markdown，用正则^```\{.cpp file=(\S+)\}$匹配带file=标记的代码块，并把块内容写成同名.h文件。lca.md中的{.cpp file=lca}代码块因此会被抽取为lca.h，供测试程序#include "lca.h"使用。
2. 测试用例：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() { vector<vector<int>> 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++ -std=c++17 -fsanitize=undefined -fno-sanitize-recover编译并执行；全部断言通过则输出绿色Passed，任一测试失败则汇总报错并以非零退出码结束。仓库中的 test/clean.sh 负责清理抽取产生的*.h临时文件。

从源码结构可以推断，这套「Markdown 代码块 ↔ 头文件 ↔ 测试驱动」的流水线是仓库中所有算法文章共用的验证机制：文档即源码、源码即可测，既保证了文章示例不漂移，也让读者可以随时自行复现实验。

应用与延伸

LCA 是树结构问题的「基础设施」，在仓库中还有大量直接相关的延伸阅读：

• 倍增法 LCA：lca_binary_lifting.md 提供 $O(N \log N)$ 预处理、$O(\log N)$ 查询的另一种主流实现，不依赖 RMQ 数据结构，常与本文方案互补；
• 离线 Tarjan / RMQ 线性实现：仓库中的 lca_tarjan.md（Tarjan 离线 LCA）与 lca_farachcoltonbender.md（Farach–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 模板。

• 文档
• 教程
• 知识库