倍增
易错提醒
首先强调一下，倍增不是一种算法，它是一种思想，而像什么 RMQ 问题啊，ST 表啊，都是由倍增思想演变出来的一种算法。接下来我们来正式的接入今天的话题
什么是倍增
倍增，倍增，顾名思义，就是以一个数成倍的增长，这个数通常是2。当然也会有在不同的时候会以其他的数进行翻倍，比如3，8，16等等，但是都不常见。我们现在就先来讲讲倍增中的线性倍增。
线性倍增
倍增一般情况下就是用来求解某一区间的极值，或一个成倍增长的数。
引入——快速幂与倍增的关联
快速幂和倍增也有一点点的关联，我们知道快速幂是通过二进制分解的形式来计算的，而倍增也是构成二进制位权的方法。
区间极值问题
给定一个长度为 n n n 的区间，给定 m m m 次询问，每次询问有两个值 l , r l,r l,r 代表一个区间的左右端点，请给出这个区间的最大值。
上述问题就是一个区间极值问题，而区间极值问题就是 RMQ 问题，我们这里不要抛开本质的倍增而只去关注算法。我们要把两者结合起来看。
首先，如果让你去求一个区间的极值，你会怎么求？是不是只能去枚举每一段，然后求一个最大值？这样的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2) ，相比之下，有点高。那么我们可以怎么弄呢？
我们这里要先了解一个二进制数的特性：所有的实数都可以被写成若干个二进制相加，也就是说，我们可以采用二进制的方式去表达每个数。基于此，我们的每段区间都可以分成若干个，长度为
2
k
2^k
2k 的区间，那么我们只需要对在这些区间中找一个最大值不就完了？
那么我们现在的问题就转化到了如何求解每段长度为 2 k 2^k 2k 的区间的最大值呢？和如何利用这些区间去求得每个区间的极值？
问题1——如何预处理
问题描述：如何求解每段长度为 2 k 2^k 2k 的区间的最大值
子问题1
这里我们考虑使用动态规划。
首先我们知道，动态规划一定是从最优解到最优解，所以我们这里要先知道当前是2的多少倍，所以我们应该先枚举指数
i
i
i ，其次，我们还需要知道每一段的起点和终点，所以我们还要去枚举起点
j
j
j （注意：这里
j
j
j 的范围应该是
1
≤
j
≤
n
+
1
−
2
i
1 \le j \le n+1-2^i
1≤j≤n+1−2i ，因为这是一个区间）
那么我们就可以得到以下代码
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}
2k−1 的区间，又因为我们是先枚举的指数，所以
2
k
−
1
2^{k-1}
2k−1 的两个答案我们是知道的，所以我们只需要在两个答案中选一个最大的（或最小的）就行了。
只不过我们还需要知道这两段分别的起点。
这里我们可以画一个图来了解一下
由图可见，第一段是
j
→
j
+
2
k
−
1
−
1
j \to j+2^{k-1}-1
j→j+2k−1−1 ，第二段是
j
+
2
k
−
1
→
j
+
2
k
−
1
j+2^{k-1} \to j+2^k-1
j+2k−1→j+2k−1 ，所以，两端的起点分别是
j
j
j 和
j
+
2
k
−
1
j+2^{k-1}
j+2k−1 。基于此，我们就可以写出以下状态转移方程
d
p
[
i
]
[
k
]
=
m
a
x
(
d
p
[
i
]
[
k
−
1
]
,
d
p
[
i
+
2
k
−
1
]
[
k
−
1
]
)
dp[i][k]=max(dp[i][k-1],dp[i+2^{k-1}][k-1])
dp[i][k]=max(dp[i][k−1],dp[i+2k−1][k−1])
现在我们也是成功的预处理出来了每一段长为 2 k 2^k 2k 的区间的最大值，样例代码如下：
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 ( n l o g n ) O(nlogn) O(nlogn)
问题2——如何求解每个区间的极值
我们已经解决了预处理的问题了，现在我们就要去处理每个区间的问题了。这里我们就要用到前面所提到的一个定理，所有的实数都可以被写成若干个二进制相加。我们可以基于这个定理去求解每个区间的极值。
我们可以采取函数
l
o
g
2
log2
log2 来求解当前这段所包含的最大的长度为
2
k
2^k
2k 的
k
k
k ，然后从大到小依次枚举可行的指数
j
(
1
≤
j
≤
k
)
j(1\le j \le k)
j(1≤j≤k) ，然后不断更新起点
x
x
x ，并且通过这个起点
x
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 ( l o g n ) O(logn) O(logn)
除此之外，还有一个时间复杂度是
O
(
1
)
O(1)
O(1) 的方法，但是在有些时候不能用，要小心加谨慎，高危 。
因为我们知道，我们求得是最大值，所以有重复也没有关系，那么一旦我们知道了当前区间的最大的
k
k
k ，那么我们是否也可以直接在前面找一个长度为
2
k
2^k
2k 的区间，后面也找一个长度为
2
k
2^k
2k 的区间就行了？只不过后面的区间的起点我们还要算一下罢了，这里就不算了，直接给出答案。
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
≤
n
≤
5
×
1
0
4
)
n(1\le n\le 5\times 10^4)
n(1≤n≤5×104) 头牛总是按同一序列排队。
有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 q ( 1 ≤ q ≤ 1.8 × 1 0 5 ) q(1\le q\le 1.8\times10^5) q(1≤q≤1.8×105) 个可能的牛的选择和所有牛的身高 h i ( 1 ≤ h i ≤ 1 0 6 , 1 ≤ i ≤ n ) h_i(1\le h_i\le 10^6,1\le i\le n) hi(1≤hi≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。
输入格式
第一行两个数 n , q n,q n,q。
接下来 n n n 行，每行一个数 h i h_i hi。
再接下来 q q q 行，每行两个整数 a a a 和 b b b，表示询问第 a a a 头牛到第 b b b 头牛里的最高和最低的牛的身高差。
输出格式
输出共
q
q
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&l