Skip to content

倍增

什么是?

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

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

实现

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

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

f(p,k) 表示在 p 点跳 2k

如果满足条件就令:

p=p+2k,k=k+1

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

否则就:

k=k1

直到 k=0 停止下来

运用

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

网站基于vitepress主题open17💙