作用

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)$。

下面给出完整的代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define Sparse_Table ST
using namespace std;
class Sparse_Table
{
	#define MAXN 233333
    #define MAXEXPO 32
    //这边列表示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;
}