ST表（Sparse Table）：
它是一种动态规划的方法，实际上也是RMQ问题。以最小值为例。a为所寻找的数组，用一个二维数组f(i,j)记录区间[i,i+2^j-1]区间中的最小值。其中f[i,0] = a[i];所以，对于任意的一组(i,j)，f(i,j) = min{ f (i,j-1),f (i+2^(j-1),j-1) }来使用动态规划计算出来。这个算的高明之处不是在于这个动态规划的建立，而是它的查询：它的查询效率是O(1)！如果不细想的话，怎么弄也是不会想到有O（1）的算法的。假设我们要求区间[m,n]中a的最小值，找到一个数k使得2^k< n-m+1，即k=[ln(b-a+1)/ln(2)] 这样，可以把这个区间分成两个部分：[m,m+2^k-1]和[n-2^k+1,n]！我们发现，这两个区间是已经初始化好的！前面的区间是f(m,k)，后面的区间是f(n-2^k+1,k)！这样，只要看这两个区间的最小值，就可以知道整个区间的最小值！
小结： 稀疏表(SparseTable)算法是O(nlogn)+O(1)的，对于查询很多大的情况下比较好。
ST算法预处理：用dp[i,j]表示从i开始的，长度为2^j 的区间的RMQ，则有递推式dp[i,j]=min{dp[i,j-1],dp[i+2^(j-1), j-1]}即用两个相邻的长度为2^(j-1)的块，更新长度为2^j的块。因此，预处理时间复杂度为O(nlogn)。这个算法记录了所有长度形如2k的所有询问的结果。从这里可以看出，稀疏表算法的空间复杂度为 O(nlogn)。
代码：
#pragma comment(linker, "/STACK:102400000,102400000") //#include<bits/stdc++.h> #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<map> #include<cmath> #include<queue> #include<set> #include <utility> #include<stack> using namespace std; typedef long long ll; typedef unsigned long long ull; #define mst(a) memset(a, 0, sizeof(a)) #define M_P(x,y) make_pair(x,y) #define rep(i,j,k) for (int i = j; i <= k; i++) #define per(i,j,k) for (int i = j; i >= k; i--) #define lson x << 1, l, mid #define rson x << 1 | 1, mid + 1, r const int lowbit(int x) { return x&-x; } const double eps = 1e-8; const int INF = 1e9+7; const ll inf =(1LL<<62) ; const int MOD = 1e9 + 7; const ll mod = (1LL<<32); const int N = 1010; const int M=100010; template <class T1, class T2>inline void getmax(T1 &a, T2 b) {if(b>a)a = b;} template <class T1, class T2>inline void getmin(T1 &a, T2 b) {if(b<a)a = b;} int read() { int v = 0, f = 1; char c =getchar(); while( c < 48 || 57 < c ){ if(c=='-') f = -1; c = getchar(); } while(48 <= c && c <= 57) v = v*10+c-48, c = getchar(); return v*f; } int a[50001]; int f[50001][16]; int n; void RMQ_init() //建立： dp(i,j) = min{dp(i,j-1),dp(i+2^(j-1),j-1):O(nlogn) { for(int i=1; i<=n; i++) f[i][0] = a[i]; int k=floor(log((double)n)/log(2.0)); //C/C++取整函数ceil()大,floor()小 for(int j=1; j<=k; j++) for(int i=1;i<=n;i++) //for(int i=n; i>=1; i--) //有些题能AC，有些不能 { if(i+(1<<j)-1<=n) //f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } int RMQ(int i,int j) //查询：返回区间[i,j]的最小值:O(1) { int k = floor(log((double)(j-i+1))/log(2.0)); return min(f[i][k],f[j-(1<<k)+1][k]); } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); RMQ_init(); printf("%d\n",RMQ(2,5)); return 0; }
