倍增法

  |  

摘要: 倍增法原理、代码模板、例题与应用场景

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


$1 倍增法算法思想

在递推状态的时候,只递推状态空间中 2 的幂次,当需要求其它位置的时候,利用以下性质,可以用此前求过的 2 的幂次上的状态现算出来

1
任意整数可以表示成若干个 2 的幂次的和

这种算法称为倍增法。倍增法与二进制划分结合可以降低很多问题的时间和空间复杂度,例如快速幂,倍增优化DP

模型问题1

长度为 $N$ 的数列 $A[0..N-1]$,处理在线 $Q$ 个查询:每次给定一个整数 $T$,求最大的 $k$ 使得 $A$ 中前 $k$ 个数的和 $\sum\limits_{i=0}\limits^{k-1}A[i] \leq T$,其中 $0 \leq T \leq \sum\limits_{i=0}\limits^{N-1}A[i]$。

算法1

每次询问都对 $k$ 进行 $O(N)$ 的枚举,总 $O(NQ)$。

算法2

预处理前缀和 S[i] := A[0..i-1],每次查询,二分 k,通过比较 S[k] 和 T 的关系调整 K 的上下界。总 $O(N+Q\log N)$。

算法3:倍增法

1
2
3
4
5
6
7
8
p = 1, k = 0, sum = 0
求 A[k..k+p-1] 的和(共p个数), 结果为 S[k + p] - S[k]
若 sum + S[k + p] - S[k] <= T,则
累加上这 p 个数的和,然后将 p 的跨度增长一倍
sum += S[k + p] - S[k], k += p, p *= 2
若 sum + S[k + p] - S[k] > T,则
不累加,p /= 2 再试
当 p 为 0 时,k 为答案

倍增法

模型问题2

这是一个交互问题。

您有一个升序整数数组,其长度未知。您没有访问数组的权限,但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i):

返回数组第ith个索引(0-indexed)处的值(即 secret[i]),或者如果 i 超出了数组的边界,则返回 $2^{31} - 1$

你也会得到一个整数 target。

如果存在 secret[k] == target,请返回索引 k 的值;否则返回 -1

你必须写一个时间复杂度为 $O(\log n)$ 的算法。

提示:

1
2
3
1 <= secret.length <= 1e4
-1e4 <= secret[i], target <= 1e4
secret 严格递增

示例 1:
输入: secret = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中,下标为 4

示例 2:
输入: secret = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不在数组中所以返回 -1

算法:倍增法

由于数组有序,可以考虑二分的方法。但这里数组的长度未知,二分的算法不好实现。但可以通过倍增法处理。

从数组最左边 A[0] 往右走,每一步走 step,也就是上一步访问 A[i],走一步之后访问 A[i+step]。初始时 step = 1

假设当前访问了 i 位置的数据 A[i],并且 A[i] < target,此时我们考虑下一个数据 A[i + step]

  • 如果当前访问的 A[i + step] == target 那么就找到了;
  • 如果 A[i + step] < target,那么 target 的位置在 i + step 的右边,向右走 i += step,然后将 step 翻倍;
  • 如果 A[i + step] > target,那么 target 的位置在 i + step 的左边,不能向右走,而是将 step 减半。

代码 (C++, 模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int search(const ArrayReader& reader, int target) {
int i = 0, step = 1;
if(reader.get(0) == target)
return 0;
while(step > 0)
{
int cur = reader.get(i + step);
if(cur == target)
return i + step;
else if(cur < target)
{
i += step;
step *= 2;
}
else
step /= 2;
}
return -1;
}
};

$2 倍增法应用场景

1. 快速幂

参考文章:

2. LCA

参考文章:

3. RMQ

参考文章:

4. 倍增优化DP

参考文章:

5. 多重背包

参考文章:

6. 后缀数组

参考文章:

$7 理想跳表

参考文章:


Share