二进制倍增

这与快速幂是同一个思想：任何步数都是若干个二的幂之和，只要预先备好“跳 $1,2,4,8,\dots$ 步”的答案，走 $m$ 步就化为至多 $\lfloor {\log }_{2}m\rfloor +1$ 次大跳。倍增表本身按动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。方式填充——跳 $2^{k+1}$ 步等于先跳 $2^k$ 步、再从落点跳 $2^k$ 步，恰好复用已算好的半程答案。支撑这一切的代数事实只有一条：函数复合满足结合律，因此“先分块预算、再拼接”与一步步走结果相同。与朴素逐步模拟相比是 $O(\log m)$ 对 $O(m)$ 的差距，代价是对数因子的额外内存与一次静态预处理。

取一条父指针链 $14\to 13\to \cdots \to 1$（箭头指向父亲，根 $1$ 指向自身），查询结点 $14$ 的第 $13$ 级祖先：$13=8+4+1$，依次查表 $\mathrm{up}[3][14]=6$、$\mathrm{up}[2][6]=2$、$\mathrm{up}[0][2]=1$，三次查表替代十三步逐级上爬。倍增表还可与“可结合的路径摘要”并行维护：令 $\mathrm{agg}[k][v]$ 为从 $v$ 向上 $2^k$ 步路径上的最小值（或和、最大值），其合并规则与 $\mathrm{up}$ 完全同构——这要求摘要运算构成幺半群理路幺半群Monoid具有双侧单位元的半群。，若结合律缺失，拼接便无意义。

边界情形：倍增表是静态快照，若 $f$ 会被修改（换父、改权），改变一个映射值也可能使多个起点、多个层级的表项失效，需要重建或另给动态维护算法；空间 $\mathrm{\Theta }(N\log (M+1))$ 在 $N$ 很大时不可忽视，而“第 $k$ 级祖先”这类特定问题另有更省空间的线性预处理算法，倍增胜在简单与通用。另一常用技巧是在表上自高位向低位“贪心下探”：例如当前节点满足谓词，且沿向根方向谓词先真后假时，可逐位尝试仍为真的大跳，寻找最靠近根的真祖先。必须同时限制不超过实际深度，避免根自环制造不存在的更远祖先。这个结论依赖谓词沿链单调；返回位置正是真区间向根一侧的边界。

树上的最近公共祖先理路最近公共祖先Lowest common ancestor · LCA有根树中同时为两个顶点祖先且深度最大的唯一顶点及其查询问题。是倍增的招牌应用：先把较深点提到同一深度；若两点已经相同，立即返回该点。否则从高位到低位，只在两点的 $2^k$ 级祖先不同时让它们同时跳过去，最后返回任一点的父亲。每次跳跃都停在 LCA 下方，因而不会越过答案。若接口只问第 $k$ 级祖先，Level Ancestor 问题理路Level Ancestor 问题Level ancestor problem · LA query · 层祖先问题在静态根树中按目标深度或向上步数返回唯一祖先，并比较倍增的对数查询与线性空间常数查询方案。还能在静态树上追求线性空间与常数查询；若目标是 LCA，RMQ–LCA 等价理路RMQ 与 LCA 的等价归约RMQ-LCA equivalence · RMQ to LCA reduction用 Euler 深度序列与 Cartesian tree 建立静态 RMQ 和 LCA 的双向线性归约。给出另一条线性预处理路线。倍增的 $O(N\log (M+1))$ 预处理与 $O(\log (M+1))$ 查询是静态 RAM 下的最坏界，胜在构造直接，而非所有树查询上的最终界。

稀疏表理路稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。把同一“按二的幂分块”思想用于静态区间查询，数与矩阵的快速幂是它在乘法结构上的化身。并行环境中的指针跳跃与链表排名理路指针跳跃与链表排名pointer jumping · pointer doubling · list ranking同步倍增后继指针并累加跨越距离，在对数轮内求链表节点到表尾的排名。也反复把后继距离加倍，但评价指标变成总工作与并行深度。函数图上的第 $m$ 个后继、树上路径摘要仍属于顺序查表版本；共享“doubling”图像不表示这些成本模型相同。