ST算法用于求解RMQ問題，即區間最大最小值。通過預處理使得每次查詢的時間復雜度為O(1)

算法分析
因為要求最大值和最小值，所以用兩個二維數組來記錄。FMax[i][j] 表示以第i個數為起點，i+2^j-1為終點的連續2^j個數中的最大值（FMin同理，下文略）。顯然，FMax[i][0] = A[i]。

FMax[i][j] 所表示的區間一定可以二等分為兩段長度均為2^j-1的區間，即
[i, i+2^j-1 -1] 和 [i+2^j-1, i+2^j-1]，顯然，FMax[i][j]就是兩小段各自最大值里邊的較大值，即

FMax[i][j] = max(FMax[i][j-1], FMax[i + (1<<(j-1))][j-1]);

預處理的方法是按照區間遞增順序，由小區間遞推得到大區間FMax[i][j]。
查詢代碼非常簡練，根據左右邊界算出長度取2的對數k=log2(r-l+1),2^k小于等于區間長度，然后

return max(FMax[l][k], FMax[r-(1<<k)+1][k]);

這里的原理是兩個小區間的并集等于所求區間。

模板代碼

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; const int MAXN = 100000; int n; int A[MAXN]; // 規定該數組從1開始計數 int FMin[MAXN][20], FMax[MAXN][20]; // F[i][j]表示以i為起點，連續2^j個數里的最值 void Init() {for (int i = 1; i <= n; i++) FMin[i][0] = FMax[i][0] = A[i];for (int j = 1; (1<<j) <= n; j++) // 按區間長度遞增順序遞推{for (int i = 1; i + (1<<j) - 1 <= n; i++) // 區間起點{FMin[i][j] = min(FMin[i][j-1], FMin[i + (1<<(j-1))][j-1]);FMax[i][j] = max(FMax[i][j-1], FMax[i + (1<<(j-1))][j-1]);}} } int Query(int l, int r) {int k = (int)log2(r-l+1); // 區間長度 >= 2^k// 從左起點往右走2^k，從右終點往左走2^k，取兩區間并集（即所求區間）的最值return max(FMax[l][k], FMax[r-(1<<k)+1][k]); // 查詢最小值用min即可 } int main() {int a, b;cin >> n;for (int i = 1; i <= n; i++) cin >> A[i];Init();while (cin >> a >> b) cout << Query(a, b) << endl;return 0; } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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