浅说倍增算法——线性倍增

倍增

易错提醒

首先强调一下，倍增不是一种算法，它是一种思想，而像什么 RMQ 问题啊，ST 表啊，都是由倍增思想演变出来的一种算法。接下来我们来正式的接入今天的话题

什么是倍增

倍增，倍增，顾名思义，就是以一个数成倍的增长，这个数通常是2。当然也会有在不同的时候会以其他的数进行翻倍，比如3，8，16等等，但是都不常见。我们现在就先来讲讲倍增中的线性倍增。

线性倍增

倍增一般情况下就是用来求解某一区间的极值，或一个成倍增长的数。

引入——快速幂与倍增的关联

快速幂和倍增也有一点点的关联，我们知道快速幂是通过二进制分解的形式来计算的，而倍增也是构成二进制位权的方法。

区间极值问题

给定一个长度为 $n$ 的区间，给定 $m$ 次询问，每次询问有两个值 $l,r$ 代表一个区间的左右端点，请给出这个区间的最大值。

上述问题就是一个区间极值问题，而区间极值问题就是 RMQ 问题，我们这里不要抛开本质的倍增而只去关注算法。我们要把两者结合起来看。
首先，如果让你去求一个区间的极值，你会怎么求？是不是只能去枚举每一段，然后求一个最大值？这样的时间复杂度是 $O(n^2)$ ，相比之下，有点高。那么我们可以怎么弄呢？
我们这里要先了解一个二进制数的特性：所有的实数都可以被写成若干个二进制相加，也就是说，我们可以采用二进制的方式去表达每个数。基于此，我们的每段区间都可以分成若干个，长度为 $2^k$ 的区间，那么我们只需要对在这些区间中找一个最大值不就完了？

那么我们现在的问题就转化到了如何求解每段长度为 $2^k$ 的区间的最大值呢？和如何利用这些区间去求得每个区间的极值？

问题1——如何预处理

问题描述：如何求解每段长度为 $2^k$ 的区间的最大值

子问题1

这里我们考虑使用动态规划。
首先我们知道，动态规划一定是从最优解到最优解，所以我们这里要先知道当前是2的多少倍，所以我们应该先枚举指数 $i$ ，其次，我们还需要知道每一段的起点和终点，所以我们还要去枚举起点 $j$ （注意：这里 $j$ 的范围应该是 $1\le j\le n+1-2^i$ ，因为这是一个区间）
那么我们就可以得到以下代码

for (int i=1;(1<<i)<=n;i++){for (int j=1;j+(1<<i)-1<=n;j++){//状态转移}
}

我们现在知道了如何枚举，接下来就是如何进行转移了。

子问题2

上面我们讲了，动态规划是从最优解到最优解，再加上我们是以2的倍数进行分段的，所以我们其实可以把当前的区间分成两个小的区间，也就是分成两个长度为 $2^{k-1}$ 的区间，又因为我们是先枚举的指数，所以 $2^{k-1}$ 的两个答案我们是知道的，所以我们只需要在两个答案中选一个最大的（或最小的）就行了。
只不过我们还需要知道这两段分别的起点。
这里我们可以画一个图来了解一下

由图可见，第一段是 $j\to j+2^{k-1}-1$ ，第二段是 $j+2^{k-1}\to j+2^k-1$ ，所以，两端的起点分别是 $j$ 和 $j+2^{k-1}$ 。基于此，我们就可以写出以下状态转移方程
$$dp[i][k]=max(dp[i][k-1],dp[i+2^{k-1}][k-1])$$

现在我们也是成功的预处理出来了每一段长为 $2^k$ 的区间的最大值，样例代码如下：

for (int i=1;i<=n;i++){cin>>a[i];dp1[i][0]=a[i];//注意要提前预处理
}
for (int i=1;(1<<i)<=n;i++){for (int j=1;j+(1<<i)-1<=n;j++){dp1[j][i]=max(dp1[j][i-1],dp1[j+(1<<(i-1))][i-1]);}	
}

这样的时间复杂度为 $O(nlogn)$

问题2——如何求解每个区间的极值

我们已经解决了预处理的问题了，现在我们就要去处理每个区间的问题了。这里我们就要用到前面所提到的一个定理，所有的实数都可以被写成若干个二进制相加。我们可以基于这个定理去求解每个区间的极值。

我们可以采取函数 $log2$ 来求解当前这段所包含的最大的长度为 $2^k$ 的 $k$ ，然后从大到小依次枚举可行的指数 $j(1\le j\le k)$ ，然后不断更新起点 $x$ ，并且通过这个起点 $x$ ，来确定当前是哪一段的答案，在根据可选的答案中选一个最大值。
样例代码如下：

cin>>x>>y;
int num=log2(y-x+1)+1;//多加一个，保险
for (int j=num;j>=0;j--){if (x+(1<<j)-1<=y){maxn=max(dp[x][j],maxn);x+=(1<<j);//更新起点}
}
cout<<maxn;

这样的时间复杂度是 $O(logn)$

除此之外，还有一个时间复杂度是 $O(1)$ 的方法，但是在有些时候不能用，要小心加谨慎，高危 。
因为我们知道，我们求得是最大值，所以有重复也没有关系，那么一旦我们知道了当前区间的最大的 $k$ ，那么我们是否也可以直接在前面找一个长度为 $2^k$ 的区间，后面也找一个长度为 $2^k$ 的区间就行了？只不过后面的区间的起点我们还要算一下罢了，这里就不算了，直接给出答案。

cin>>x>>y;
int num=log2(y-x+1);
maxn=max(dp[x][num],dp[y-(1<<num)+1][num]);
cout<<maxn;

但是这种方法只适用于求解可以重复的题目，如果当前题目要求的是传递到第几个人这种就不可以了。

例题

[USACO07JAN] Balanced Lineup G

题目描述
每天,农夫 John 的 $n(1\le n\le 5\times 10^4)$ 头牛总是按同一序列排队。

有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 $q(1\le q\le 1.8\times 10^5)$ 个可能的牛的选择和所有牛的身高 $h_i(1\le h_i\le 10^6,1\le i\le n)$。他想知道每一组里面最高和最低的牛的身高差。

输入格式

第一行两个数 $n,q$。

接下来 $n$ 行，每行一个数 $h_i$。

再接下来 $q$ 行，每行两个整数 $a$ 和 $b$，表示询问第 $a$ 头牛到第 $b$ 头牛里的最高和最低的牛的身高差。

输出格式
输出共 $q$ 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。

样例 #1
样例输入 #1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出 #1

6
3
0

这道题就是典型的倍增的题目，只不过是要求一个最大值和一个最小值，可以用来练手。

#include<bits/stdc++.h>
using namespace std;
const int INF=5*1e5+10;
long long a[INF],dp1[INF][40],dp2[INF][40];
int main(){int n,q;cin>>n>>q;for (int i=1;i<=n;i++){cin>>a[i];dp1[i][0]=a[i];dp2[i][0]=a[i];}for (int i=1;(1<<i)<=n;i++){for (int j=1;j+(1<<i)-1<=n;j++){dp1[j][i]=max(dp1[j][i-1],dp1[j+(1<<(i-1))][i-1]);dp2[j][i]=min(dp2[j][i-1],dp2[j+(1<<(i-1))][i-1]);}}for (int i=1;i<=q;i++){long long maxn=INT_MIN,minn=INT_MAX;int x,y;cin>>x>>y;int num=log2(y-x+1);maxn=max(dp1[x][num],dp1[y-(1<<num)+1][num]);minn=min(dp2[x][num],dp2[y-(1<<num)+1][num]);cout<<maxn-minn<<endl;}return 0;
}

Pass An Note

题目描述
有 $n$ 个小朋友在传纸条，编号 $1$ 至 $n$。编号为 $i$ 的小朋友如果收到了纸条，会传给编号为 $a_i$ 的小朋友。

现在有 $m$ 组询问，每组询问会给出参数 $p$ 和 $q$，问从小朋友 $p$ 开始，传 $q$ 次纸条会传到哪个小朋友手里。请求出每组询问的答案。
输入格式
第一行输入两个正整数 $n$ 和 $m$，保证$n\le 3\times 10^5$ ，$m\le 3\times 10^5$。

第二行输入 $n$ 个正整数 $a_i$ ，保证 $1\le ai\le n$ 接下来 $m$ 行，每行两个正整数 $p$ 和 $q$，保证 $1\le p,q\le n$ 。

输出格式
输出 $m$ 行，每行一个正整数，表示从 $p$传递 $q$ 次纸条会到达的人。

样例输入

10 10
5 2 10 4 9 4 8 10 6 2
5 3
5 7
7 10
8 2
8 1
7 7
8 1
5 4
3 5
9 4

样例输出

4
4
2
2
10
2
10
4
2
4

这道题就不能使用上述的 $O(1)$ 的方法了，所以我们还是老老实实的敲 $O(logn)$ 的方法吧。

#include<bits/stdc++.h>
using namespace std;
const int INF=5*10e5;
int a[INF],dp[INF][20];//dp表示从x开始传，传2^i次 
int main(){int n,m;cin>>n>>m;for (int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i][0]=a[i];}for (int i=1;(1<<i)<=n;i++){for (int j=1;j<=n;j++){dp[j][i]=dp[dp[j][i-1]][i-1];}} while (m--){int x,y,ans;scanf("%d %d",&x,&y);int num=log2(y)+1;for (int i=num;i>=0;i--){if ((1<<i)<=y){ans=dp[x][i];x=ans;y-=(1<<i);}}printf("%d\n",ans);}return 0;
}