定义

st 表是用于解决可重复贡献问题的数据结构。

例如：GCD，RMQ 等

这里讲一讲 RMQ

RMQ

RMQ 是指区间最值问题，即区间最小值以及区间最大值。

st 表可以在 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的时间内建立，以 O ( 1 ) O(1) O(1) 的效率进行查询。

以维护区间最大值为例吧。

S t e p . 1 Step.1 Step.1

定义 d p i , j dp_{i,j} dpi,j​ 表示以第 i i i 个数开始，长度为 2 j 2^j 2j 的区间的最大值。

数学表示为： max ⁡ { a k } , { k , k ∈ [ i , i + 2 j − 1 ] } \max\{a_k\},\{k,k\in{[i,i+2^j-1]}\} max{ak​},{k,k∈[i,i+2j−1]}

很显然，对于 d p i , 0 dp_{i,0} dpi,0​ 的值就为 a i a_i ai​。

我们可以发现可以采取倍增的思想，这个值就为这个区间左边一块的最大值和右边一块的最大值，那么为：

d p i , j ← max ⁡ { d p i , j − 1 , d p i + 2 j − 1 , j − 1 } dp_{i,j} \gets \max\{dp_{i,j-1},dp_{i+2^{j-1},j-1}\} dpi,j​←max{dpi,j−1​,dpi+2j−1,j−1​}

很显然我们第一维需要从小到大枚举 j j j，而且不能使其越界。

code：

void init(){
	for(int i=1;i<=n;i++) dp[i][0]=a[i];
	for(int j=1;j<=24;j++)
		for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

S t e p . 2 Step.2 Step.2

我们来试着如何查询。

我们假设查询的区间为： [ l , r ] [l,r] [l,r]

我们假设有一个正整数 k k k，满足 2 k ≤ r − l + 1 2^k\le r-l+1 2k≤r−l+1 和 2 k + 1 ≥ r − l + 1 2^{k+1}\ge r-l+1 2k+1≥r−l+1

这个 k k k 就是我们确定的合适的长度。

然后查询即为： max ⁡ { d p l , k , d p r − 2 k + 1 , k } \max\{dp_{l,k},dp_{r-2^{k}+1,k}\} max{dpl,k​,dpr−2k+1,k​}

这样我们发现虽然我们查询有相交的，但是并不影响查询最大值，问题因此解决。

code：

int ask(int l,int r){
	int v=log2(r-l+1);
	return max(dp[l][v],dp[r-(1<<v)+1][v]);
}

练习

P2048 超级钢琴

思路：固定一个端点，找到所有的最优解，然后利用 RMQ 找到次优解。利用优先队列找到前 k k k 大。

P2471 [SCOI2007]降雨量

思路：根据条件把关系给推出来，然后挨个判断，st 表在本题只是个工具。

CF475D CGCDSSQ

题解