ST表（Sparse Table）

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。

下面是一些基本的操作：

//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]);
}