2023/04/ST表算法与代码实现

前言

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

ST表思想与原理

ST表的核心思想是倍增，设连续区域为$[L,R]$，若将连续区域分为左右两半，左半部分的最值为$max_{L}$,右半部分的最值为$max_R$ 。整个连续区域的最值就为左、右两个区域中最值的较大值也就是$max(max_L,max_R)$ 。思想如下图：

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

设f[i][j] 为从位置i开始的长为$2^j$ 区域内的最值。

$2^j=2^{j-1}+2^{j-1}$ ，我们将长度为$2^j$ 的区域均分为两段，分别长为$2^{j-1}$ 。那么整个长为$2^j$ 区域的最值就为左、右两段长为$2^{j-1}$区域最值的较大值。设区域从位置i开始，那么整个区域的最值可表达为f[i][j] ；

左侧长为$2^{j-1}$区域的最值可表示为f[i][j-1] ；再来看右侧区域，先求出右侧区域的起始位置为$i+(1<<(j-1))$ ,右侧长为$2^{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$也就是$Lg=log_2^{R-L+1}$ 。关系为$2^{Lg}<=R-L+1$ 。

设$L\leq x \leq y \leq R$

那么区域$[L,R]$ 的最值可以看做$max(max_{[L,y]},max_{[x,R]})$， 两个区域可以有重叠部分。我们设$[L,y]$ 和$[x,R]$ 区间长度均为$2^{Lg}$ ，那么$max_{[L,y]}=f[L][Lg]$ ；$max_{[x,R]}=f[R-(1<<Lg)+1][Lg]$。

综合，$max_{[L,r]}=max(f[l][Lg],f[r-(1<<Lg)+1][Lg])$ 。

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]。