倍增

什么是?

倍增能够使得线性的处理转化为对数级的处理，大大地优化时间复杂度

与其说倍增是算法,不如说它是一种思想,它能够帮助我们优化算法

实现

不难看出,任意整数都可以被表示为若干个2的次幂项的和

因此我们可以把原问题划分为多个2次幂,常见的表示方法为

设 $f(p,k)$ 表示在 $p$ 点跳 $2^k$ 步

如果满足条件就令:

$$p=p+2^k,k=k+1$$

并且加上这次的 $f(p,k)$ 的贡献

否则就:

$$k=k-1$$

直到 $k=0$ 停止下来

运用

• 快速幂
• ST表
• 倍增LCA
• ...