binary lifting · O(log n) 查询

树上倍增：按二进制位往上跳

换到树上。给定一棵有根树，反复回答「 $u$ 与 $v$ 最深的那个公共祖先是谁」，这个问题叫 LCA（lowest common ancestor）。

朴素解法很直接：两点各自沿 parent 爬到根，第一个共同出现的节点就是答案。单次代价是树高，而树高最坏是 $n-1$ 。一条链上问相邻两个叶子，就要爬完整棵树。本页把它降到 $O(\log n)$ 。

1 · 一步一跳为什么慢

朴素解法慢的原因不是「爬」，而是每次只能爬一级。parent 数组只回答「上一级是谁」，问「上 100 级是谁」就得连问 100 次。

这和数组上「求 $a[l..r]$ 的最小值」慢在同一处：手上只有相邻关系，跨度大的问题只能靠重复走小步凑。sparse table 的对策是预存所有 $2^k$ 长度的区间；树上的对策同样是预存所有 $2^k$ 级的跳跃。

2 · up 表

定义 2.1（倍增表） $up[k][v]$ 是 $v$ 的第 $2^k$ 级祖先。 $up[0][v]$ 就是 parent[v]；越过根记 $-1$ 。

递推与稀疏表同构：跳 $2^k$ 级等于先跳 $2^{k-1}$ 级、再跳 $2^{k-1}$ 级。

$up[k][v] = up[k-1]\big[\,up[k-1][v]\,\big]$

表的规模是 $(\lceil \log_2 n \rceil + 1) \times n$ ，建表写入 $\lceil \log_2 n \rceil \times n$ 项。 $n = 13$ 的演示树上是 $5 \times 13 = 65$ 格、52 次写入； $n = 100000$ 时是 18 层、1700000 次写入。

有了这张表，「往上 $k$ 级」就变成把 $k$ 写成二进制、按每个为 1 的位各查一次表。查表次数是 $k$ 的 popcount，至多 $\lceil \log_2 n \rceil$ 次。

图 2-1 · 第

k

级祖先按

k

的二进制位拆成若干次查表，并列出逐级爬 parent 的步数作对照。可改起点与

k

观察查表次数与跳跃落点。

3 · 查询的两个阶段

两点的深度一般不同，不能直接同步往上跳——那样跳出来的两条路径长度不等，比较「是否相等」没有意义。查询于是分两步。

第一步是对齐深度。设 $u$ 较深，深度差 $d = \text{depth}[u] - \text{depth}[v]$ 。把 $d$ 按二进制位拆开， $d$ 的第 $k$ 位为 1 就让 $u$ 跳 $2^k$ 级。跳完 $u$ 与 $v$ 同深。此时若 $u = v$ ，说明 $v$ 本来就是 $u$ 的祖先，答案已经出来了。

第二步是同步上跳。从高位到低位遍历 $k$ ，检查 $up[k][u]$ 与 $up[k][v]$ ：

两者不相等：说明跳 $2^k$ 级还没到公共祖先，跳。
两者相等：说明跳 $2^k$ 级已经跳过了 LCA（甚至更高），不跳。

遍历结束时 $u$ 与 $v$ 停在 LCA 的两个不同孩子上，答案是 $up[0][u]$ 。

图 3-1 · 倍增查询的两个阶段在树与 up 表上同步高亮，橙格 = 本步读取的表项，蓝格 = 读了并采纳。可换

u

与

v

并逐步执行。

这个「不相等才跳」的判据比它的反面好写。若改成「跳到相等就停」，得额外处理「一开始就相等」和「跳过头之后无法回退」两种情况；而按位从高到低、只在不相等时前进，天然保证了单调性：每一位跳与不跳都不会越过 LCA，最终落点必是 LCA 的孩子。演示树上一次查询读 10 到 11 个表项。 $n = 1000$ 时实测平均 22.62 个， $n = 100000$ 时 37.45 个；同步上跳阶段读满 $2(\lceil \log_2 n \rceil + 1)$ 个，即 22 与 36，多出来的零点几个来自对齐阶段那几个为 1 的位。

4 · sentinel 取值的宽松程度

越过根的位置要放一个 sentinel。 $-1$ 是最常见的写法，本系列的引擎也用它。

写这一页时的原有判断是：sentinel 必须是所有节点共用的同一个值，否则同步上跳阶段的「 $up[k][u] \ne up[k][v]$ 」会误判——两点都跳出了树，用各自的自环会得到两个不同的值，于是被当成「还没到公共祖先」而继续跳。

实测推翻了这一点。把 sentinel 换成自环（ $up[k][\text{root}] = \text{root}$ ）重跑三棵 40 节点随机树的全部 1600 个点对，答案与 $-1$ 版本逐个相同。原因在于同步上跳阶段的两个点深度相同且都在 LCA 之下，跳 $2^k$ 级要么都还在树内、要么都被自环钉在根上，两种情形下等与不等的判断都成立；而对齐阶段跳的级数不超过深度差，深的那一方根本不会跳出树。所以本页这个 sentinel 是实现风格问题，不是正确性条件。

注 · 上面这条只对本页这个「不相等才跳」的写法成立。若实现里有别的地方直接判 up[k][v] === -1 来决定是否继续，换成自环就会死循环，那时 sentinel 的选择又变成了正确性条件。结论依附于写法，不能单独搬走。

5 · 这套方案的位置

倍增的优点是短。一张二维表、两个循环，不需要欧拉序、不需要并查集，改一处就能顺带支持「第 $k$ 级祖先」「路径上的最大边权」这类问题：把 $up[k][v]$ 旁边再挂一个 $\text{maxw}[k][v]$ ，查询时顺路取 $\max$ 。

它的代价是查询带一个 $\log n$ 。 $q$ 与 $n$ 同量级时，查询侧的 $2q\log n$ 会超过预处理，这时值得换成欧拉序 + RMQ 的 $O(1)$ 查询；若全部询问事先已知，Tarjan 离线连 $\log$ 都不要。

另一项代价是空间， $O(n \log n)$ 个整数。 $n = 10^6$ 时 21 层、两千一百万个 32 位整数约 84 MB，这个量级已经足以让人重新考虑方案。

6 · 参考文献

Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. In LATIN 2000: Theoretical Informatics (pp. 88–94). Springer.
cp-algorithms. Lowest Common Ancestor — Binary Lifting. https://cp-algorithms.com/graph/lca_binary_lifting.html
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed., §4.1 无向图). Addison-Wesley.