---

---

st表的作用是可以快速的得到區間內的一個最值(最大值或最小值)，不過它是靜態的，即一旦初始化不能修改。
ST表它可以做到O(nlogn)預處理，O(1)查詢最值。
ST表模板:
f[i][j]表示從i開始，長度是2^j的區間長度中最大值是多少

const int N=1e5+1; int n,mx[N][20],mn[N][20],a[N]; int getmx(int l,int r){//區間[l,r]內的最大值int tmp=log2(r-l+1);return max(mx[l][tmp],mx[r-(1<<tmp)+1][tmp]); } int getmn(int l,int r){//區間[l,r]內的最小值int tmp=log2(r-l+1);return min(mn[l][tmp],mn[r-(1<<tmp)+1][tmp]); } void init()//構建ST表 {for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];for(int j=1;j<20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);}} }

P3865 【模板】ST 表
P2880 [USACO07JAN] Balanced Lineup G

總結

以上是生活随笔為你收集整理的ACM入门之【ST表/RMQ】的全部內容，希望文章能夠幫你解決所遇到的問題。

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