简介
ST表用于区间RMQ问题，它可以做到O(nlogn)预处理，O(1)查询最值。相比线段树，更加有利于静态数据的最值问题。主要是利用倍增的思想。
洛谷：P3865
模板
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <vector> using namespace std; const int MAXN = 1e6 + 10; int Max[MAXN][22]; int Min[MAXN][22]; int n,m; void QST(); int QueryMax(int ,int ); int QueryMin(int ,int ); int main() { scanf("%d%d",&n,&m); QST(); for(int i = 1;i <= m;++i) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",QueryMax(l,r)); } return 0; } void QST() { for(int i = 1;i <= n;++i) scanf("%d",&Max[i][0]); for(int i = 1;i <= n;++i) Min[i][0] = Max[i][0]; for(int j = 1;j <= 21;++j) for(int i = 1;i + (1 << j)- 1 <= n;++i) { Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]); Min[i][j] = min(Min[i][j - 1],Min[i + (1 << (j - 1))][j - 1]); } } int QueryMax(int l,int r) { int k = log2(r - l + 1); return max(Max[l][k],Max[r - (1 << k) + 1][k]); } int QueryMin(int l,int r) { int k = log2(r - l + 1); return min(Min[l][k],Min[r - (1 << k) + 1][k]); } |
