倍增

倍增法（Binary Lifting），核心思想是利用二进制拆分，预处理出跳 2⁰、2¹、2²… 步的状态，把单次大步查询拆解成若干次预计算的小步跳转，将原本线性的时间复杂度优化到对数级别，常用于 LCA、RMQ、后缀数组等问题。

January 1, 1990算法设计1分钟阅读

倍增法（Binary Lifting / Doubling Technique） 是一种在计算机科学与算法设计中非常经典且高效的思想。

它的核心核心逻辑非常简单：“成倍增长，跳跃前进”。通过利用 $2$ 的幂次方（ $1, 2, 4, 8, 16 \dots$ ），将原本需要逐位线性推导的 $O(N)$ 复杂度，大幅降低到 $O(\log N)$ 。

在日常生活中，如果让你用尽可能少的硬币凑出某个金额，或者用最少的操作步数走完一段距离，指数级递增是最快速的缩小范围方式。

倍增法建立在一个基础数学事实之上：任何正整数都可以唯一地表示为二进制数（即若干个 2 的幂次方之和）。

倍增法在图论、动态规划以及高级数据结构中有非常广泛的应用，最典型的两大应用场景如下：

在树形结构中，求两个节点的最近公共祖先，如果朴素地让较深的节点一步步向上爬，效率会比较低（退化成链时为 $O(N)$ ）。

倍增做法： 预处理出每个节点向上跳 $2^k$ 步所到达的祖先节点，定义 dp[u][k] 为节点 u 的第 $2^k$ 个祖先。
转移方程：

$\text{dp}[u][k] = \text{dp}[\text{dp}[u][k-1]][k-1]$

即：“向上跳 $2^k$ 步” 等价于 “先向上跳 $2^{k-1}$ 步，再从那个节点向上跳 $2^{k-1}$ 步”。
查询阶段： 借助预处理好的数组，先把两个节点对齐到同一深度，然后利用二进制思想从大到小（如 $2^{20}, 2^{19} \dots 2^0$ ）尝试向上跳跃，即可在 $O(\log N)$ 时间内锁定 LCA。

计算 $a^b \pmod m$ 时，如果连乘 $b$ 次，复杂度是 $O(b)$ 。

核心思想：为什么是 2 的幂次方？