倍增

介绍

倍增,即字面意思”成倍增长” 倍增的思想与二分类似,在递推时,如果状态空间很大,无法直接逐一枚举时,可以以成倍数的长度递推,因为任何一个正整数可以由若干个2的幂次相加得到,所以每次不断尝试一个范围,如果符合条件,将范围扩大一倍,反之将范围缩小到1/2,逐步逼近确定值 注意: 倍增时,状态的可行性必须时单调的,这点与二分的条件相同,倍增适用于每次枚举的范围不是很大,而总状态很大的情况,二分法在此时会因为总区间太大而超时,倍增则相对稳定一些

实现方式

1. 建立左右指针l,r,和当前的范围长度p
2. 赋初值,l=r=起始范围,p=1
3. 判断[l,r+p]是否符合条件 3.1 符合 : r=r+p,p=p*2,即将先加上这一段,继续尝试更大的区间

3.2 不符合: p=p/2,即缩小范围,再次尝试

1. 重复执行第3步,直到p=0,此时r已经达到了确切值

所以倍增实际是一个步步逼近的算法,使得程序在 log n 的时间内得出答案,n为最终答案的大小

应用

RMQ问题

RMQ问题,即区间最值问题,通过n log n的预处理,能够在O(1)的时间内得出答案

实现

预处理: Fi表示数组中以i为起点,2^j为长度的区间内的最值 计算答案: 给定[l,r]区间,答案就是 [l,l+len-1]和[r-len+1,r]中的最值,其中len为小于(r-l+1)的最大的2的幂次 原理: 因为只要求最值,所以只要两个区间能正好覆盖总区间即可,可以有重叠部分

例题

./archives/65/
./archives/66/
./archives/67/

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/71/