倍增

参考资料

• 倍增 - OI Wiki

应用

详见 ST 表。

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

例题

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

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

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

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