ST表算法与代码实现

前言

对于区间最值也就是 RMQ（Range Minimum/Maximum Query）问题，可以使用ST表（稀疏表）的方式进行离线预处理。

ST表思想与原理

ST表的核心思想是倍增，设连续区域为[L,R]，若将连续区域分为左右两半，左半部分的最值为

​,右半部分的最值为

。整个连续区域的最值就为左、右两个区域中最值的较大值也就是

​ 。思想如下图：

因为元素输入后，位置不发生改变，所以，区域最值求解后，也不会发生改变，我们可以提前预处理好。

设f[i][j] 为从位置i开始的长为

区域内的最值。

，我们将长度为

的区域均分为两段，分别长为

。那么整个长为

区域的最值就为左、右两段长为

区域最值的较大值。设区域从位置i开始，那么整个区域的最值可表达为f[i][j] ；

左侧长为

区域的最值可表示为f[i][j-1] ；再来看右侧区域，先求出右侧区域的起始位置为

,右侧长为

区域的最值可表示为f[i+(1<<(j-1))][j-1] 。

那么可推断出转移方程f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]) 。

预处理、维护过程

void stPrework(){//ST表预处理
	for(int i=1;i<=n;i++){//f[i][j]=从i开始，长为2^j区间内的最值
		f[i][0]=a[i];//长为1时的最值
	}
	for(int j=1;j<=Log[n];j++){//根据最长区间长度log[n]进行遍历
		for(int i=1;i+(1<<j)-1<=n;i++){//遍历开始位置i
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//左边的最值与右边最值中较大者为整个区域的最值
		}
	}
}

注意维护过程中j为外层循环，i为内存循环，这个不要搞反，否则会出错。原因是根据状态转移方程，f[i][j]的值，由已确定的f[?][j-1]的内容推导而来，所以需要先确定f[?][j-1]的内容，故j在外循环。

该部分复杂度为O(nlogn)

询问区域最值

而当预处理好f[][]数组后，如何求出区域最值呢？

设要求的区域为[L,R]。区域长度为R−L+1，该长度不一定为2的幂次方，我们先求出小于长度的最大的2的次方值Lg也就是

。关系为

设L≤x≤y≤R

那么区域[L,R]的最值可以看做

两个区域可以有重叠部分。我们设[L,y]和[x,R] 区间长度均为

，那么

；

综合，

int stQuery(int l,int r){//询问l~r区间的最值
	int Lg=Log[r-l+1];//计算l~r之间长度对应的log2值
	return max(f[l][Lg],f[r-(1<<Lg)+1][Lg]); 
}

这部分时间复杂度为O(1)。

总结

利用倍增的思想，离线预处理ST表，预处理部分复杂度为O(nlogn)，核心状态转移方程是f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1])；查询的复杂度为O(1),关键部分是max(f[L][Lg],f[R-(1<<Lg)+1][Lg]。

Q.E.D.