倍增算法处理区间最值（难度：***）
题目：区间最大值 方法：倍增法 题目链接：区间最大值 - 蓝桥云课 (lanqiao.cn)
思路：倍增的实现分为两步：（1）把数列按倍增划分成小区间（O(nlogn)） （2）查询任意区间的最值（O(1)）。
（1）首先定义一个二维数组dp[s][k]：表示的含义是左端点下标为s，区间长度为2^(k)的区间最值。所以很明显可以想到递推关系由k推到k-1，可以理解将一个长度为2^(k-1)长度大小的区间，通过倍增得到2^k长度大小，所以显然后者大区间的区间最值为两个小区间的区间最值合并起来，所以这就是动态规划的过程，这里由于是求区间最值所以必须将每个小区间的第一个元素初始为第一个元素，p指的是比数组大小len 小的 2 的最大倍数的对数，也即是把一个数列按倍增法划分的总组数。接下来dp遍历每个小区间，从小到大逐步递推，内层左端点下标循环的条件需要注意。初始化划分区间这里复杂度为O(nlogn)。
（2）初始化完dp数组后现在需要根据特定的区间进行查询，有了st_query函数，首先由L，R算出子区间的长度，进而算出k，查刚刚初始的dp数组就可得到子区间的最值，这里复杂度为O(1)；
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;
int n,m;
int a[maxn],dp_max[maxn][40]; //dp_min[maxn][40];
void st_init(){
for(int i=1;i<=n;i++) //初始化区间长度为1时的值
dp_max[i][0]=a[i]; //最大值。如果题目求区间最小值就改为dp_min
int p = (int)(log(double(n)) / log(2.0));
//int p=log2(n); //两者写法都行
for(int k=1;k<=p;k++) //倍增计算小区间。先算小区间，再算大区间，逐步递推
for(int s=1;s+(1<<k)<=n+1;s++)
dp_max[s][k]=max(dp_max[s][k-1], dp_max[s+(1<<(k-1))][k-1]);
//最大值。如果题目求区间最小值就改为dp_min、min
}
int st_query(int L,int R){
// int k = log2(R-L+1); //2种方法求k
int k = (int)(log(double(R-L+1)) / log(2.0));
return max(dp_max[L][k],dp_max[R-(1<<k)+1][k]);
//最大值。如果题目求区间最小值就改为dp_min、min
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
st_init();
for(int i=1;i<=m;i++){
int L,R;
scanf("%d%d",&L,&R);
printf("%d\n",st_query(L,R));
}
return 0;
}
查看3道真题和解析
投递菜鸟集团等公司10个岗位 >
网易互娱一面1人在聊