自动搬运

查看原文

来自洛谷，原作者为

	天泽龟 理想与孤独 | My Blog: http://tzturtle.moe

搬运于2025-08-24 21:53:32，当前版本为作者最后更新于2019-09-26 17:48:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

翻了很多题解没找到一篇详细图解，于是就有了这篇。

$ST$表还是很需要一篇带图解的题解吧， 定义啥的其他题解都有，就不赘述了，我们直接结合图例来理解代码。

• 预处理阶段。

1. 首先你应该知道的是，ST表是利用倍增思想来缩短时间的。而倍增就体现在他数组的定义中：对于$f[i][j]$，指的是在序列的第i项，向后$2^j$个元素所包含序列间的最大值。

对于$i=1$，我们可以画出这么一个图，其下标即为$j$：

那么对于当前$i$转移其实很明显了，我们可以直接考虑将两个小区间的答案合并，即为这个大区间的值；如图中$f[1][2]$即可由$max(f[1][1],f[3][1])$转移来。

$$f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$$

其中$2^{j-1}$也可写为$(1<<(j-1))$，这里位运算会更方便也会更快。

这个式子告诉我们，ST表类似于区间DP，是由两个小区间合并上来的。所以应该先枚举区间长度l（这里即为$j$），再枚举$i$.

2. 然后一个问题应运而生了：我们这个转移方程有没有边界呢？

不妨来看一下$i=6$的图：

可以看出在$i=6$时，$j=3$的范围是$[6,13(6+2^3)]$，已经超出了我们数据的范畴。所以当$j=3$时，$i$只能取到$[1,5(12-2^3+1)]$

由上例再根据转移方程，不难看出当$j$确定时，i的范围受限在$[1,n-2^j+1]$。

那么又根据$i=1$的情况，可知$j$应满足:

$2^j\leq n \Leftrightarrow j\leq lg[n]$，其中$lg[n]$表示n关于底数2的对数向下取整，可以递推求得。

最终附上预处理代码：

	scanf("%d%d",&n,&m); lg[1]=0;
	for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    //求lg[i]函数。
	for (int i=1;i<=n;i++) scanf("%d",&f[i][0]);
	for (int j=1;j<=lg[n];j++)
	for (int i=1;i<=n-(1<<j)+1;i++){ //注意两个边界
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}	

时间复杂度为$O(N·logN)$

---

• 求最值阶段。

我们现在来求红色标记区间$[L,R]$的最值。如果要最大化利用ST表，仍应该考虑类似处理ST表的方法，将该区间分成 两个ST表可直接维护的小区间，然后二者求最值即可。

• 那对于起始点，我们找一段ST表在该区间内可覆盖的，最大的子区间，由数学语言可描述为：

$(L+2^k-1<=R) \Leftrightarrow (k<=lg[R-L+1])$ 那我们直接取等,令$j=k$即可~

于是对于起始点点在ST表里的取值即为：$f[L][k]$

• 对于终止点，我们反向找一个与起始点要求相同的子区间，由于对称性，此时k仍为起始点求得的$k=lg[R-L+1]$

但是我们应该如何确定该子区间的起点呢？由于子区间长度为$2^k$，设起点在$D$处，则满足：

$(D+2^k-1=R) \Leftrightarrow (D=R-2^k+1)$

于是对于终止点在ST表里的取值即为：$f[D][k]$，可证明这样一定可以覆盖整个区间。

综上，对于区间$[L,R]$求其最值，不难发现答案即为：

$$\max(f[L][k],f[R-(1<<k)+1][k])$$

接下来是一个例子：

对于蓝色区间，我们先找到$k=lg[8-2+1]=lg[7]=2$，则两个子区间即为：$[2,5],[5,8]$，对应了$f[2][2],f[5][2]$，两个取最值即可。

附上求值部分代码：

	for (int i=1;i<=m;i++)
	{
		cin>>x>>y; int l=lg[y-x+1];
		cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
	}

• 后记

虽说是详细图解，但好像更偏向于一些简单的数学证明。。

ST表对于RMQ问题还是有很大的使用空间，希望各位能好好掌握。

最后附上我丑陋的代码：

#include <iostream>
using  namespace std;

int n,m,x,y,a[100010],lg[100010],f[100010][20];

int main()
{
	cin>>n>>m; lg[1]=0;
	for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n;i++) cin>>f[i][0];
	for (int j=1;j<=lg[n];j++)
	for (int i=1;i<=n-(1<<j)+1;i++){
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	
	
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y; int l=lg[y-x+1];
		cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
	}
}