形式陈述

对有限状态上的函数 $f$，预计算

$$up[k][v]=f^{2^k}(v),up[k+1][v]=up[k][up[k][v]].$$

若需要计算 $f^m(v)$，按 $m$ 的二进制位依次应用相应跳表。预处理 $O(N\log M)$，每次跳转 $O(\log M)$。 树的第 $2^k$ 级祖先是最常见实例。

直觉

大步数由二进制位组成；预先知道“跳 1、2、4、8……步”后，可像快速幂一样组合任意步数。

例子与边界

它可处理函数图、祖先查询和带可结合路径摘要的跳转。若状态转移随时间改变，静态倍增表会失效。

推论与应用

它连接快速幂、稀疏表、LCA 和函数迭代。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), binary lifting.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), binary lifting.