浅谈倍增
本篇随笔浅谈一下倍增。
一、倍增法的概念
倍增法是一种优化递推枚举的方法。
有的时候递推的状态空间很大。
倍增采取的策略就是，在递推的时候只维护(2^k,kin Z)的状态。对于其他状态，由于一个数可以被二进制分解成若干个二的整数次幂的和的形式，所以其他的状态就也可以使用已经维护出来的状态来维护了。
二、倍增的一些应用
RMQ问题的ST表算法。
树上倍增。
（LCA）
关于树上倍增，蒟蒻有专门的博客讲解：
本篇随笔浅谈一下倍增。
倍增法是一种优化递推枚举的方法。
有的时候递推的状态空间很大。
倍增采取的策略就是，在递推的时候只维护(2^k,kin Z)的状态。对于其他状态，由于一个数可以被二进制分解成若干个二的整数次幂的和的形式，所以其他的状态就也可以使用已经维护出来的状态来维护了。
RMQ问题的ST表算法。
树上倍增。
（LCA）
关于树上倍增，蒟蒻有专门的博客讲解：