倍增

参考资料

• 倍增 - OI Wiki

简介

倍增（Binary Lifting）的核心思想是：预处理以 $2$ 的整次幂为步长的状态，然后将任意目标分解为若干 $2$ 的幂次之和，逐段合并得到答案。这利用了「任意非负整数均可用二进制表示」这一性质。

预处理阶段，设 $f(i,x)$ 表示从状态 $x$ 走 $2^i$ 步后的结果，则递推关系为：

$$f(i,x)=f(i-1,f(i-1,x))$$

预处理复杂度为 $O(n\log n)$，每次查询 $O(\log n)$。

应用

详见 ST 表。

详见 最近公共祖先（LCA）。

例题

洛谷 P3865 【模板】ST 表 && RMQ 问题

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

洛谷 P3379 【模板】最近公共祖先（LCA）

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。