倍增 本页面将简要介绍倍增法。
简介 倍增法(英语:binary lifting),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。
这个方法在很多算法中均有应用,其中最常用的是 RMQ 问题和求 LCA(最近公共祖先) 。
RMQ 问题 参见:RMQ 专题
RMQ 是 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。使用倍增思想解决 RMQ 问题的方法是 ST 表 。
树上倍增求 LCA 参见:最近公共祖先
例题 题 1 例题 如何用尽可能少的砝码称量出 [0,31] 之间的所有重量?(只能在天平的一端放砝码)
解题思路 答案是使用 1 2 4 8 16 这五个砝码,可以称量出 [0,31] 之间的所有重量。同样,如果要称量 [0,127] 之间的所有重量,可以使用 1 2 4 8 16 32 64 这七个砝码。每次我们都选择 2 的整次幂作砝码的重量,就可以使用极少的砝码个数量出任意我们所需要的重量。
为什么说是极少呢?因为如果我们要量出 [0,1023] 之间的所有重量,只需要 10 个砝码,需要量出 [0,1048575] 之间的所有重量,只需要 20 个。如果我们的目标重量翻倍,砝码个数只需要增加 1。这叫“对数级”的增长速度,因为砝码的所需个数与目标重量的范围的对数成正比。
题 2 例题 给出一个长度为 n 的环和一个常数 k ,每次会从第 i 个点跳到第 (i+k)\bmod n+1 个点,总共跳了 m 次。每个点都有一个权值,记为 a_i ,求 m 次跳跃的起点的权值之和对 10^9+7 取模的结果。
数据范围: 1\leq n\leq 10^6 , 1\leq m\leq 10^{18} , 1\leq k\leq n , 0\le a_i\le 10^9 。
解题思路 这里显然不能暴力模拟跳 m 次。因为 m 最大可到 10^{18} 级别,如果暴力模拟的话,时间承受不住。
所以就需要进行一些预处理,提前整合一些信息,以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话,不论是时间还是空间都难以承受。
那么应该如何预处理呢?看看第一道例题。有思路了吗?
回到本题。我们要预处理一些信息,然后用预处理的信息尽量快的整合出答案。同时预处理的信息也不能太多。所以可以预处理出以 2 的整次幂为单位的信息,这样的话在预处理的时候只需要处理少量信息,在整合的时候也不需要大费周章。
在这题上,就是我们预处理出从每个点开始跳 1、2、4、8 等等步之后的结果(所处点和点权和),然后如果要跳 13 步,只需要跳 1+4+8 步就好了。也就是说先在起始点跳 1 步,然后再在跳了之后的终点跳 4 步,再接着跳 8 步,同时统计一下预先处理好的点权和,就可以知道跳 13 步的点权和了。
对于每一个点开始的 2^i 步,记录一个 go[i][x]
表示第 x 个点跳 2^i 步之后的终点,而 sum[i][x]
表示第 x 个点跳 2^i 步之后能获得的点权和。预处理的时候,开两重循环,对于跳 2^i 步的信息,我们可以看作是先跳了 2^{i-1} 步,再跳 2^{i-1} 步,因为显然有 2^{i-1}+2^{i-1}=2^i 。即我们有 sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]]
,且 go[i][x] = go[i-1][go[i-1][x]]
。
当然还有一些实现细节需要注意。为了保证统计的时候不重不漏,我们一般预处理出“左闭右开”的点权和。亦即,对于跳 1 步的情况,我们只记录该点的点权和;对于跳 2 步的情况,我们只记录该点及其下一个点的点权和。相当于总是不将终点的点权和计入 sum。这样在预处理的时候,只需要将两部分的点权和直接相加就可以了,不需要担心第一段的终点和第二段的起点会被重复计算。
这题的 m\leq 10^{18} ,虽然看似恐怖,但是实际上只需要预处理出 65 以内的 i ,就可以轻松解决,比起暴力枚举快了很多。用行话讲,这个做法的 时间复杂度 是预处理 \Theta(n\log m) ,查询每次 \Theta(\log m) 。
参考代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 #include <cstdio>
using namespace std ;
const int mod = 1000000007 ;
int modadd ( int a , int b ) {
if ( a + b >= mod ) return a + b - mod ; // 减法代替取模,加快运算
return a + b ;
}
int vi [ 1000005 ];
int go [ 75 ][ 1000005 ]; // 将数组稍微开大以避免越界,小的一维尽量定义在前面
int sum [ 75 ][ 1000005 ];
int main () {
int n , k ;
scanf ( "%d%d" , & n , & k );
for ( int i = 1 ; i <= n ; ++ i ) {
scanf ( "%d" , vi + i );
}
for ( int i = 1 ; i <= n ; ++ i ) {
go [ 0 ][ i ] = ( i + k ) % n + 1 ;
sum [ 0 ][ i ] = vi [ i ];
}
int logn = 31 - __builtin_clz ( n ); // 一个快捷的取对数的方法
for ( int i = 1 ; i <= logn ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
go [ i ][ j ] = go [ i - 1 ][ go [ i - 1 ][ j ]];
sum [ i ][ j ] = modadd ( sum [ i - 1 ][ j ], sum [ i - 1 ][ go [ i - 1 ][ j ]]);
}
}
long long m ;
scanf ( "%lld" , & m );
int ans = 0 ;
int curx = 1 ;
for ( int i = 0 ; m ; ++ i ) {
if ( m & ( 1 << i )) { // 参见位运算的相关内容,意为 m 的第 i 位是否为 1
ans = modadd ( ans , sum [ i ][ curx ]);
curx = go [ i ][ curx ];
m ^= 1l l << i ; // 将第 i 位置零
}
}
printf ( "%d \n " , ans );
}
build 本页面最近更新: ,更新历史 edit 发现错误?想一起完善? 在 GitHub 上编辑此页! people 本页面贡献者:Ir1d, ShadowsEpic, Fomalhauthmj, siger-young, MingqiHuang, Xeonacid, hsfzLZH1, orzAtalod, NachtgeistW copyright 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用