倍增
倍增思想举例
A、B 两点之间相隔若干单位为 1 的距离，如何从最快地从 A 走到 B？
朴素的想法是：因为 A B 之间距离未知，只能从A开始，每次走1步，看看走多少步能到达B，这样的时间复杂度是 O(N) 的
实际上可以只记录走1, 2, 4, 8, 16步能到达的地方
从 A 出发：
若跳 8 个格子（超过B了，放弃）
若跳 4个格子（超过B了，放弃）
若跳 2个格子（没超过B，可以跳）
说明 A 到 B 的距离一定能够在 [2, 4) 之间
其实思路就是二分的逆向
倍增其它应用
LCA 最近公共祖先
不同于按层遍历树，使用倍增的话就是跳着遍历层。比如层数为 N，则先查第 N 层，再查 N/2 层，以此类推
快速幂
给出 x, y, p，求 x^y%p，如果 x, y 的数据很大的话，O(N) 的算法会超时，那么这时候我们可以用倍增的方法减少运算次数
先求出
对于任意一个 y, x^y 都可以由上面的项做乘积得到（不过是几十次运算），这样就大大减少了运算次数
比如要算 x^17，就别乘 17次 x 了，先算出 x^2，再算出 x^4，再算 x^8、x^16、x^32，发现 x^32 过大，回到 x^16 开始尝试
Range Minimum/Maximum Query 区间最值问题
给出 N 个数组成的数列，q 次询问，每次给出 x, y 问区间 [x, y] 之间的最小值是多少？
如果直接暴力的话复杂度 O(N*q)，q 很大的话，复杂度也很高
RMQ算法也是用到了倍增的方法
f(i,1) 表示从第 i 个位置开始，往后 1个数的最小值 f(i,2) 表示从第 i 个位置开始，往后 2个数的最小值 f(i,3) 表示从第 i 个位置开始，往后 4个数的最小值
如 f(0, 8) = f(0, 4) + f(4, 2) + f(6, 1) + f(7, 1)
则递推式即为 f(i, k) = min( f(i, 2^(k-1)), f(i+2^(k-1), 2^(k-2)), ..., f(i+ 2^k-1 + 2^k-1 ... +1, 1) )
时间复杂度为 O(NlogN + q)
Last updated