倍增法求 LCA(Binary Lifting)

倍增法(Binary Lifting,又称二进制提升)是求树上两节点最近公共祖先(LCA)的经典方法。它预处理每个节点向上第二的零次、一次、二次幂步的祖先,构成一张跳表,查询时利用二进制拆分把大距离的上移拆成若干次二的幂次跳跃,从而在对数时间内定位最近公共祖先。

概述

最近公共祖先指树中两个节点共同祖先里深度最大的那个,是许多树上问题的基础操作。倍增法以空间换时间,预处理量与节点数乘对数成正比,单次查询仅需对数时间,实现直观、常数较小,是竞赛与工程中最常用的 LCA 方案之一。

核心原理

• 预处理跳表:记录每个节点向上二的 k 次方步的祖先,其中二的 k 次方步祖先等于其二的 k 减一次方步祖先再向上跳同样步数,可递推填表。
• 对齐深度:查询两点时先把较深的节点按二进制拆分向上跳,使两点深度相同。
• 同步上跳:若此时两点已相同则它即为答案;否则两点一起从高到低尝试跳二的幂次,只要跳后不相遇就跳,最终它们的父节点即为最近公共祖先。
• 扩展用途:跳表还能顺带维护路径上的最值、和等信息,支持带权祖先查询。

应用场景

倍增法广泛用于求树上路径信息、判断祖先关系、计算两点距离、树上差分、以及可持久化与在线查询场景。它与树链剖分、欧拉序加稀疏表等方法并列,是解决树上祖先类问题的主流工具,也常作为更复杂树上算法的子过程。

常见问题

问:倍增法和欧拉序加稀疏表求 LCA 哪个更好?答:稀疏表方法单次查询为常数时间但预处理稍复杂,倍增法查询为对数时间但实现简单且易于扩展维护路径信息,实际按需求选择。

问:为什么同步上跳时要求跳后不相遇才跳?答:这样能保证两点始终停在最近公共祖先的正下方而非越过它,最后取父节点即得到精确的最近公共祖先。