ST表

\(\text{ST}\) 表是用于解決可重復貢獻問題的數據結構。

• 可重復貢獻問題：區間按位和、區間按位或、區間 \(\gcd\) 、區間最大、區間最小等滿足結合律且可重復統計的問題。

模板預處理：(以區間最大值為例)

void pre_work() {for(int i=2;i<=n;i++) lg2[i]=lg2[i/2]+1;pow2[0]=1;for(int i=1;i<=lg2[n];i++) pow2[i]=pow2[i-1]*2;for(int i=1;i<=n;i++) st[0][i]=val[i];for(int i=1;i<=lg2[n];i++)for(int j=1;j<=n+1-pow2[i];j++)st[i][j]=max(st[i-1][j],st[i-1][j+pow2[i-1]]); } int query(int l,int r) {int p=lg2[r-l+1];return max(st[p][l],st[p][r+1-powr[p]]); }

RMQ

總結

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

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