|
多余的文字就不多赘述了，直接上代码，边看边解释。（这小编也太烂了吧，算了，将就将就吧）
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/*
建表时间o(nlogn),查询时间o(1)
不支持在线更新
*/
class ST
{
private:
int dp[10000][30]; //dp[i][j]表示从第i个元素开始，长度为2的j次方这个区间的的最值
void build(int nums[],int len)
{
//先初始化长度为1的最值，以后长度为2,4,8....
for(int i=1;i<=len;i++) dp[i][0]=nums[i-1]; //以i为开头，长度为1的区间的最值
int k=(int)(log(len*1.0)/log(2.0));
//2^k<=len<2^(k+1)
for(int j=1;j<=k;j++) //每次区间的长度设计为2的j次方
{
for(int i=1;i<=len-(1<<j)+1;i++) //i+length => i+(1<<j)-1<=n
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
}
}
public:
ST(int nums[],int len)
{
build(nums,len);
}
int query(int left,int right)
{
left++,right++; //满足从下标0开始检索
int k=(int)(log(right-left+1)/log(2.0));
//2^k<=right-left+1<2^(k+1)
//所以从left开始向右覆盖一个长度为2^k区间,和从right向左覆盖一个
//长度为2^k的一个区间一定会覆盖完整个left到right区间，可能会有重叠
//但是一定不会超过[left,right]区间，所以对答案无影响
return max(dp[left][k],dp[right-(1<<k)+1][k]);
}
};
int main()
{
int len=8;
int nums[]={3,5,1,10,7,9,3,2};
ST my_st=ST(nums,len);
cout<<my_st.query(0,7);
return 0;
}
还是比较简单易懂的吧。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/*
建表时间o(nlogn),查询时间o(1)
不支持在线更新
*/
class ST
{
private:
int dp[10000][30]; //dp[i][j]表示从第i个元素开始，长度为2的j次方这个区间的的最值
void build(int nums[],int len)
{
//先初始化长度为1的最值，以后长度为2,4,8....
for(int i=1;i<=len;i++) dp[i][0]=nums[i-1]; //以i为开头，长度为1的区间的最值
int k=(int)(log(len*1.0)/log(2.0));
//2^k<=len<2^(k+1)
for(int j=1;j<=k;j++) //每次区间的长度设计为2的j次方
{
for(int i=1;i<=len-(1<<j)+1;i++) //i+length => i+(1<<j)-1<=n
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
}
}
public:
ST(int nums[],int len)
{
build(nums,len);
}
int query(int left,int right)
{
left++,right++; //满足从下标0开始检索
int k=(int)(log(right-left+1)/log(2.0));
//2^k<=right-left+1<2^(k+1)
//所以从left开始向右覆盖一个长度为2^k区间,和从right向左覆盖一个
//长度为2^k的一个区间一定会覆盖完整个left到right区间，可能会有重叠
//但是一定不会超过[left,right]区间，所以对答案无影响
return max(dp[left][k],dp[right-(1<<k)+1][k]);
}
};
int main()
{
int len=8;
int nums[]={3,5,1,10,7,9,3,2};
ST my_st=ST(nums,len);
cout<<my_st.query(0,7);
return 0;
}
|
楼主
标题置顶
标题高亮
