ST表
结构体版，函数版
luogu3865
倍增的思想
不支持更改，建表是nlogn
然后查询是
两个部分重叠比较，O（1）
支持操作
1.init 初始化
2.query 查询
struct ST_RMQ { int mn[M][31]; void init() { for(int j = 1;(1<<j) <= n; j ++) for(int i = 1; i + (1 << j) <= n + 1; i ++) mn[i][j] = max(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]); } int query(int ql, int qr) { int k = (log2(r - l + 1)); return max(mn[ql][k], mn[qr - (1 << k) + 1][k]); } }
完整版
#include <cstdio> #include <algorithm> #include<cmath> using namespace std; const int M = 100000+1; int n, m, l, r; void read(int &n) { int f=1;n=0;char s=getchar(); while('9'<s||s<'0'){if(s=='-')f=-1;s=getchar();} while('0'<=s&&s<='9'){n=n*10+s-'0';s=getchar();} n*=f; } struct ST_RMQ { int mn[M][31]; void init() { for(int j = 1;(1<<j) <= n; j ++) for(int i = 1; i + (1 << j) <= n + 1; i ++) mn[i][j] = max(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]); } int query(int ql, int qr) { int k = (log2(r - l + 1)); return max(mn[ql][k], mn[qr - (1 << k) + 1][k]); } } rmq; int main() { read(n);read(m); for(int i = 1; i <= n; i ++) read(rmq.mn[i][0]); rmq.init(); while(m--) { read(l);read(r); printf("%d\n", rmq.query(l, r)); } return 0; }
虽然查询很快，但建标的nlogn太伤，建议使用快读，一般cin会慢的TLE的
函数版
#include<cstdio> #include<cmath> int n,m; int a[100103],st[101000][32]; void read(int &n){ int f=1;n=0;char s=getchar(); while('9'<s||s<'0'){if(s=='-')f=-1;s=getchar();} while('0'<=s&&s<='9'){n=n*10+s-'0';s=getchar();} n*=f; } int max(int x,int y){ return x>y?x:y; } void rmq_st(){ for(int i = 1;i <= n;++ i) st[i][0]=a[i];//初始化，它本身的前缀 for(int j=1;(1<<j)<=n;++j){//这个是2^j for(int i=1;i+(1<<j)-1<=n;++i){//ST[i][j]表示那个从i开始到i+（1<<j）的最大值 st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int sum(int l, int r){ int k=(log2(r-l+1));//求log return max(st[l][k],st[r-(1<<k)+1][k]);//区间最大值在 //他右边或者左边，2^k是恰好小鱼他们之间距离的长度 //所以最大值一定包含里面，重合部分不受影响，又不是求sum } int main() { read(n);read(m); for(int i = 1;i <= n;++ i){ read(a[i]);//用a数组建一个st表 } rmq_st(); int l_, r_; while(m--){ read(l_);read(r_); printf("%d\n",sum(l_,r_)); } return 0; }
查看21道真题和解析
