ST表主要用来求解RMQ（Range Minimum/Maximum Query）问题。
ST表能够解决的问题是：
给定一个数组a[n]，动态查询数组a[l]到a[r]，即l到r范围内的最大值最小值。下面的讲解主要以最小值为主。
一、预处理
首先，我们预处理出数组stTable[i][j]，stTable[i][j]代表从a[i]元素开始（包括a[i]）连续的2^j个元素的最小值。
我们需要使用动态规划来求解stTable[i][j]，初始化为stTable[i][0]=a[i]。
其中stTable[i][j] = stTable[i][j-1] + stTable[i+2^(j-1)][j-1]。举例如下：
stTable[i][1]=a[i]+a[i+1] = stTable[i][0]+stTable[i+1][0]
stTable[i][2]=a[i]+a[i+1] +a[i+2] +a[i+3] = stTable[i][1]+stTable[i+2][0]
…….
二、求出范围[l,r]中的最小值
由于stTable[i][j]存储的信息是包含2^j个元素的，所以我们需要进行拆分或者量化，如下图：
我们把查询的区间[l,r]分别两个相交区间[l,l+2^j-1]和[r-2^j+1,r]，即stTable[l][j]和stTable[r-2^j][j]，这两个区间需要会相交，但是不影响我们求这个区间里面的最小值，即min（stTable[l][j]，stTable[r-2^j][j]）。
在给出区间[l,r]后，我们采用移位操作求出j的值，使得l+2^j-1<=r且l+2^(j+1)-1>r。
下面是一些基本的操作：
[c language=”++”]
//stTable的准备函数
void ST_Prepare(vector<int> a, vector<vector<int>>&stTable)
{
for (int i = a.size()-1; i >=0; i–)
{
//初始化0
stTable[i][0] = a[i];
//使用动态规划计算出stTable
for (int j=1; i + (1<<j) -1 < a.size(); j++)
{
stTable[i][j] = min(stTable[i][j – 1], stTable[i + (1<<(j-1)) ][j – 1]);
}
}
}
int queryMin(int l, int r, vector<vector<int>>&stTable)
{
int len = r – l + 1;
int k = 0;
int tmpLen = len;
//求出合适的指数k
while (tmpLen != 1)
{
k++;
tmpLen = (tmpLen >> 1);
}
return min(stTable[l][k], stTable[r – (1 << k) + 1][k]);
}
[/c]