> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/algorithm/bei-zeng.md).

# 倍增

#### 倍增思想举例

A、B 两点之间相隔若干单位为 1 的距离，如何从最快地从 A 走到 B？

朴素的想法是：因为 A B 之间距离未知，只能从A开始，每次走1步，看看走多少步能到达B，这样的时间复杂度是 `O(N)` 的

实际上可以只记录走1, 2, 4, 8, 16步能到达的地方

从 A 出发：

1. 若跳 8 个格子（超过B了，放弃）
2. 若跳 4个格子（超过B了，放弃）
3. 若跳 2个格子（没超过B，可以跳）

说明 A 到 B 的距离一定能够在 \[2, 4) 之间

其实思路就是二分的逆向

### 倍增其它应用

#### LCA 最近公共祖先

不同于按层遍历树，使用倍增的话就是跳着遍历层。比如层数为 `N`，则先查第 `N` 层，再查 `N/2` 层，以此类推

#### 快速幂

给出 `x, y, p`，求 `x^y%p`，如果 `x, y` 的数据很大的话，`O(N)` 的算法会超时，那么这时候我们可以用倍增的方法减少运算次数

先求出

$$
x^1, x^2, x^4, x^8.....
$$

对于任意一个 `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)`