ST表的原理及其实现
ST表类似树状数组，线段树这两种算法，是一种用于解决RMQ(Range Minimum/Maximum Query,即区间最值查询)问题的离线算法
与线段树相比，预处理复杂度同为O(nlogn),查询时间上，ST表为O(1),线段树为O(nlogn)
st表的主体是一个二维数组st[i][j]，表示需要查询的数组的从下标i到下标i+2^j - 1的最值，这里以最小值为例
预处理函数：
int a[];//原始输入数组
int st[][];//st表 void init(int n)
{
for (int i = ; i < n; i++)
st[i][] = a[i]; for (int j = ; ( << j) <= n; j++)
{
for (int i = ; i + ( << j) - < n; i++)
st[i][j] = min(st[i][j - ],st[i + ( << (j - ))][j - ]);
}
}
这里首先把从0~n-1的2^0部分进行覆盖，再往下继承
继承这里也很好理解，我们以一个长度为5的数组[5,1,2,3,4]为例
2^0部分覆盖过去自然是5，4，3，2，1
2^1部分的长度为4，从0一直到3，因为从下标为4开始后面只有他自己
st[0][1]是下标为0~1的最小值，自然也就是st[0][0]和st[1][0]的最值
以此往下类推我们可以得出结论：
st[i][j] = min(st[i][j - 1],st[i + 2^(j - 1))][j - 1])
到这里初始化就完成了，注意下标不要越界，如果你对为什么这么处理有困惑的话，请继续看查询
查询函数这里不太好理解
初始化时，每一个状态对应的区间长度都为2^j，由于给出的查询区间长度不一定恰好为2^j，
所以我们要引出一个定理：2^log(a)>a/2 。
因为log(a)表示小于等于a的2的最大几次方。
比如说log(4)=2,log(5)=2,log(6)=2,log(7)=2,log(8)=3,log(9)=3…….
那么我们要查询x到y的最小值。
设len=y-x+1,t=log(len)
根据上面的定理：2^t>len/2
从位置上来说，x+2^t越过了x到y的中间！
因为位置过了一半
所以x到y的最小值可以表示为min(从x往后2^t的最小值，从y往前2^t的最小值)
前面的状态表示为mn[t][x]
设后面（从y往前2^t的最小值）的初始位置是k，
那么k+2^t-1=y，所以k=y-2^t+1
所以后面的状态表示为mn[t][y-2^t+1]
所以x到y的最小值表示为min(mn[t][x],mn[t][y-2^t+1])，所以查询时间复杂度是O（1）
int search(int l, int r)
{
int k = (int)(log((double)(r - l + )) / log(2.0));
return min(st[l][k],st[r - ( << k) + ][k]);
}
示例程序：
#include <iostream>
#include <algorithm> using namespace std; int a[];//原始输入数组
int st[][];//st表 void init(int n)
{
for (int i = ; i < n; i++)
st[i][] = a[i]; for (int i = ; ( << i) <= n; i++)
{
for (int j = ; j + ( << i) - < n; j++)
st[j][i] = min(st[j][i - ],st[j + ( << (i - ))][i - ]);
}
} int search(int l, int r)
{
int k = (int)(log((double)(r - l + )) / log(2.0));
return min(st[l][k],st[r - ( << k) + ][k]);
} int main()
{
int n,m;
while (cin >> n >> m)
{
for (int i = ; i < n; i++)
cin >> a[i]; init(n); while (m--)
{
int l, r;
cin >> l >> r;
cout << search(l,r) << endl;;
}
}
return ;
}