作用
- ST算法是用来求解给定区间的最值的
优势
- ST算法分成两部分：离线预处理 $O(nlogn)$和 在线查询$O(1)$。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。
操作
预处理
- 就是DP， 用于求解区间最值，并保存到一个二维数组中
- 使用倍增的思想，每次增加2^i个长度
使用$f[i,j]$表示以$i$为起点，区间长度为$2^j$的区间最值，此时区间为$[i,i + 2^j - 1]$。
比如，$f[0,2]$表示区间$[0,3]$的最小值，即等于$4$，$f[2,2]$表示区间$[2,5]$的最小值，即等于$1$。
在求解$f[i,j]$时，ST算法先对长度为$2^j$的区间$[i,i + 2^j - 1]$分成两等份，每份长度均为$2^{j - 1}$。之后在分别求解这两个区间的最值$f[i,j - 1]$和$f[i + 2^{j - 1},j - 1]$。，最后在结合这两个区间的最值，求出整个区间的最值。特殊情况，当$j = 0$时，区间长度等于$1$，即区间中只有一个元素，此时$f[i,0]$应等于每一个元素的值。
举例：要求解$f[1,2]$的值，即求解区间$[1,4] = \{4,6,10,1\}$的最小值，此时需要把这个区间分成两个等长的区间，即为$[1,2]$和$[3,4]$，之后分别求解这两个区间的最小值。此时这两个区间最小值分别对应着$f[1,1]$ 和 $f[3,1]$的值。
状态转移方程: $f[i,j] = min(f[i,j - 1],f[i + 2^{j-1},j - 1])$
初始状态为：$f[i,0] = data[i]$
求最值
已知待查询的区间$[x,y]$，求最值
我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：
（1）这两个小区间要能覆盖整个区间
（2）为了利用预处理的结果，要求小区间长度相等且都为$2^i$。注意两个小区间可能重叠。
我们可以直接得到两段区间的$i=log_2^{l-r+1}$
把待查询区间$[x，y]$分成两个小区间$[x，x + 2^i - 1]$ 和 $[y - 2^i + 1，y]$，其又分别对应着$f[x,i]$和$f[y - 2^i + 1,i]$，此时为了求解整个区间的最小值，我们只需求这两个值得最小值即可，此时复杂度是$O(1)$。
下面给出完整的代码：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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
class Sparse_Table
{
//这边列表示2的幂次，32足够int类型使用
private:
int QMax[MAXN][MAXEXPO];
int QMin[MAXN][MAXEXPO];
public:
int N;
int data[MAXN];
inline double log2(double a)
{
return (double)log(a) / log(2);
}
void initST()
{
for (register int i = 1; i <= N; i++)
for (register int j = 1; (2 << j) << N; ++j)
{
for (register int i = 1; i + (1 << j) - 1 <= N; ++i)
{
QMax[i][j] = max(QMax[i][j - 1], QMax[i + (1 << (j - 1))][j - 1]); //一定要注意是(1<<(j-1)),表示2^(j-1)
QMin[i][j] = min(QMin[i][j - 1], QMin[i + (1 << (j - 1))][j - 1]);
}
}
}
int QueryMin(int l, int r)
{
int k = log2(abs(r - l + 1));
return min(QMin[l][k], QMin[r - (1 << k) + 1][k]);
}
int QueryMax(int l, int r)
{
int k = log2(abs(r - l + 1));
return max(QMax[l][k], QMax[r - (1 << k) + 1][k]);
}
};
ST A;
int main(int argc, char **argv)
{
ios::sync_with_stdio(false);
cin >> A.N;
for (register int i = 1; i <= A.N; ++i)
cin >> A.data[i];
A.initST();
int Queries;
cout << "Enter your number of queries:" << endl;
cin >> Queries;
for (register int i = 1; i <= Queries; ++i)
{
int x, y;
cin >> x >> y;
cout << "MAXINUM Between " << x << " and " << y << " is " << A.QueryMax(x, y) << endl;
cout << "MININUM Between " << x << " and " << y << " is " << A.QueryMin(x, y) << endl;
}
return 0;
}