浅谈倍增浅谈倍增

本篇随笔浅谈一下倍增。

一、倍增法的概念

倍增法是一种优化递推枚举的方法。

有的时候递推的状态空间很大。

倍增采取的策略就是，在递推的时候只维护(2^k,kin Z)的状态。对于其他状态，由于一个数可以被二进制分解成若干个二的整数次幂的和的形式，所以其他的状态就也可以使用已经维护出来的状态来维护了。

RMQ问题的ST表算法。

树上倍增。

（LCA）

关于树上倍增，蒟蒻有专门的博客讲解：