ST表（区间查询

本文主要是介绍ST表（区间查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解决的问题：

• 数组区间查询最大值和最小值
• 对于解决数组的树状数组的区间修改 ------- 线段树
• 倍增思想

核心代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int num[N];
int f[N][N];
int main(){int n;cin>>n;//输入默认从1开始 for(int i=1;i<=n;i++) cin>>num[i];//创建st表for(int i=0;i<=20;i++){//枚举区间长度 2*i次方//2的20次方大约1.04e6 //当区间太大  会一直continue for(int j=1;j+(1<<i)-1<=n;j++){//区间末尾：j+2的i次方-1 不能越界 f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);//j到j+1<<i-1区间 由两个一半的区间组成//所以时间复杂度为nlogn }} //查询函数//给定左右闭区间l,R 查询最大值 int l,r;cin>>l>>r;int qujian=log2(r-l+1);//查看区间长度对应的log图//通过先分裂区间后 利用区间交集的方式去查询//记得左右  会用到lr  右边不能从l入手  从r入手 int res=max(f[l][qujian],f[r-(1<<qujian)+1][qujian]);cout<<res<<endl;return 0; }

这篇关于ST表（区间查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---