前言

对于区间最值也就是 RMQRange Minimum/Maximum Query)问题,可以使用ST表(稀疏表)的方式进行离线预处理。

ST表思想与原理

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

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

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

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

左侧长为2j12^{j-1}区域的最值可表示为f[i][j-1] ;再来看右侧区域,先求出右侧区域的起始位置为i+(1<<(j1))i+(1<<(j-1)) ,右侧长为2j12^{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)O(nlogn)

询问区域最值

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

设要求的区域为[L,R][L,R]。区域长度为RL+1R-L+1 ,该长度不一定为2的幂次方,我们先求出小于长度的最大的2的次方值LgLg也就是Lg=log2RL+1Lg=log_2^{R-L+1} 。关系为2Lg<=RL+12^{Lg}<=R-L+1

LxyRL\leq x \leq y \leq R

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

综合,max[L,r]=max(f[l][Lg],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)O(1)

总结

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

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)