st表的作用是可以快速的得到區間內的一個最大值，不過它是靜態的，即一旦初始化不能修改。

https://www.luogu.com.cn/problem/P3865

#include<bits/stdc++.h> using namespace std; const int N=200010,M=21; int n,m; int w[N]; int f[N][M]; void init()//初始化 {for(int j=0;j<M;j++)for(int i=1;i+(1<<j)-1<=n;i++)if(!j) f[i][j]=w[i];else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); } int query(int l,int r)//查詢 {int len=r-l+1;int k=log(len)/log(2);return max(f[l][k],f[r-(1<<k)+1][k]); } int main(void) {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&w[i]);init();while(m--){int l,r; scanf("%d%d",&l,&r);printf("%d\n",query(l,r));} }

總結

以上是生活随笔為你收集整理的P3865 【模板】ST 表【又称RMQ】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。