倍增

简单介绍

倍增并不具体指某一个算法，而是指一种思路。
这种思路在很多地方有类似的应用，比如LCA，ST表，后缀数组等。
这个算法似乎并没有

可以预处理出每个节点的 $2^j$ 阶祖先。
如果求 $x$ 和 $y$ 的最近公共祖先，可以先将 $x$ 和 $y$ 中深度较深的节点调整到和较浅的深度相同，对于两个深度相同的不同节点来说，同时向上跳，会在LCA处相遇。

初始以 $O(n \log n)$ 的时间预处理所有长度为 $2$ 的次幂的区间的最值。
对于任意一个询问，都可以用两个长度为 $2$ 的次幂的区间拼出询问所需的区间。
代码和细节请参考ST

可以通过倍增求后缀数组。
相当于依次排序所有长度为 $1, 2, 4, 8, \ldots$ 的子串。
每次排序可以用计数排序实现。
代码和细节请参考后缀数组

可以依次求出 $x^1, x^2, x^4, x^8, \ldots$ 的结果
如果需要 $x^n$ 的结果，可以把 $n$ 拆分成 $2$ 的次幂的和，从 $x^{2^{i}}$ 中选择一些乘起来。

这个方法不仅可以用于整数的情况，也可以用于矩阵，排列，多项式等。
代码和细节请参考快速幂。

Atcoder Beta Ranking
可以看到翻页功能是用倍增实现的，这样你可以只按 $\log(n)$ 次就跳转到自己想去的页面。
（显然正常人都会直接修改地址栏里的页码）

Luogu P1081
倍增，预处理每个点向后跳 $2^j$ 步后的结果

Luogu P1084
倍增，每个节点尽可能往根节点走。

Luogu P1967
先求MST，然后相当于问两个点之间路径的边权最小值是多少。
倍增记录 $2^j$ 阶祖先的同时，也记录到祖先的最小边权是多少。

Luogu P2609
倍增，从 $(A_i, A_{i+1})$ 可以推出 $(A_{i+1}, A_{i+2})$ 或者 $(A_{2i}, A_{2i+1})$ 。
相当于每次可以乘二或者是加一。