一、定义
ST表的功能很简单
它是解决RMQ问题(区间最值问题)的一种强有力的工具
它可以做到O(nlogn)预处理，O(1)查询最值
二、算法
ST表是利用的是倍增的思想
拿最大值来说
我们用Max[i][j]表示，从i位置开始的2j个数中的最大值，例如Max[i][1]表示的是i位置和i+1位置中两个数的最大值
那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值（注意这里的编号是从1开始的）
查询的时候也比较简单
我们计算出log2(区间长度)
然后对于左端点和右端点分别进行查询，这样可以保证一定可以覆盖查询的区间
刚开始学的时候我不太理解为什么从右端点开始查的时候左端点是r−2k+1
实际很简单，因为我们需要找到一个点x，使得x+2k−1=r
这样的话就可以得到x=r−2k+1
（1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。
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时，区间长度等于0，即区间中只有一个元素，此时F[i,0]应等于每一个元素的值。
（2）在线查询：对给定区间进行分割，借助该二维数组求最值
在线处理：这里我们是已知待查询的区间[x,y]，求解其最值。
在预处理期间，每一个状态对应的区间长度都为2^i。由于给出的待查询区间长度不一定恰好为2^i，因此我们应对待查询的区间进行处理。
这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：
（1）这两个小区间要能覆盖整个区间
（2）为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int map[1000005][20];
int n;
void work()
{
int i,j;
for(j=1;1<<j<=n;j++)
for(i=1;i+(1<<j)-1<=n;i++)//i+(1<<j)-1<=n是为了保证区间左端点不超出总数n
map[i][j]=min(map[i][j-1],map[i+(1<<j-1)][j-1]);//实质是动态规划
}
int question(int z,int y)
{
int x=int (log(y-z+1)/log(2));//注意y-z要加一才为区间长度
return min(map[z][x],map[y-(1<<x)+1][x]);//分别以左右两个端点为基础，向区间内跳1<<x的最
//大值;
}
int main()
{
scanf("%d",&n);//输入数据总数
int i,a,b,k;
for(i=1;i<=n;i++)
scanf("%d",&map[i][0]);//数据输入加初始化，即从i开始向右走2的0次方的区间中的最大值，（注//意i到i的长度为一）。
work();//预处理
scanf("%d",&k);//输入询问次数k
for(i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",question(a,b));//输出结果
}
return 0;
} 三、例题
https://www.luogu.org/problemnew/show/P3865（题解：https://www.luogu.org/problemnew/solution/P3865）
京公网安备 11010502036488号