Binary Lifting

定义 Definition

Binary lifting（二进制倍增/二进制跳跃）：一种常用于树与图算法的预处理技巧，通过把“第 \(2^k\) 次跳跃能到哪里”提前算好（如祖先、父节点、下一状态），使得查询（例如求第 k 个祖先、LCA 最近公共祖先、函数迭代跳转）能在 \(O(\log n)\) 时间内完成。

发音 Pronunciation (IPA)

/ˈbaɪnəri ˈlɪftɪŋ/

例句 Examples

Binary lifting lets you find the k-th ancestor of a node in O(log n).
二进制倍增可以在 O(log n) 时间内找到某个节点的第 k 个祖先。

After preprocessing the parent table with binary lifting, we answered thousands of LCA queries efficiently even on a large tree.
用二进制倍增预处理好祖先表后，即使在很大的树上，我们也能高效回答成千上万次 LCA 查询。

词源 Etymology

binary 表示“二进制/二分”的思想（以 2 为底的幂次划分），lifting 在算法语境里可理解为“把一步一步的移动，提升为按倍数跳跃”。该术语在竞赛编程与算法教材中常用，用来描述用 \(2^0, 2^1, 2^2, \dots\) 的跳跃长度来加速查询的做法。

相关词 Related Words

• Ancestor
• Lca
• Doubling
• Sparse Table
• Tree
• Preprocessing
• Logarithmic
• Dynamic Programming

文献与作品 Literary / Notable Works

• Competitive Programming 3（Steven Halim 等）：以“倍增/二进制跳跃”思路讲解树上祖先与 LCA 等经典查询。
• CP Handbook（Antti Laaksonen）：介绍树算法与对数级查询技巧，常与 binary lifting 思路一同出现。
• Introduction to Algorithms（CLRS，相关章节）：虽然不一定以该术语命名，但在树上跳跃、对数分解与预处理思想上有相通内容。