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