ST 表学习笔记

标签：log minn int 代码笔记 ST 学习 dp

什么是 ST 表

ST 表，即 Sprase Table，也叫稀疏表。
它主要用于解决 RMQ（Range Minimum/Maximum Query，区间最值查询）问题。

更生动地讲，ST 表就是在 \(O(n \log n)\) 的时间里预处理个表，然后可以在 \(O(1)\) 的时间内查询一个区间的最大值或最小值。

ST 表本质上是动态规划。

建造 ST 表

与线段树、树状数组一样，ST 表要先建造。

假设我们需要求区间最小值。

设 \(dp_{i, j}\) 表示以 \(i\) 为头，长度为 \(2^j\) 的区间的最小值。

例如，\(dp_{5, 2}\) 表示 \([5, 8]\) 的元素的最小值。

int dp[数组大小 N][log(N)+5];

如 \(N = 10^5\)，就可以定义成： int minn[100005][20]。

首先初始化，令 \(dp_{i, 0} = a_i\) 即可。

for (int i = 1; i <= n; i++) minn[i][0] = read();

* 程序中为了区分是求最大值还是最小值，将 dp 改成了 minn。不过终究是个名字罢了，不用在意。

状态转移方程很简单：\(dp_{i, j} = \min(dp[i][j-1], dp[i+2^{j-1}][j-1])\)。

原因更简单，长度为 \(2^j\) 的最值就是两段长度为 \(2^{j-1}\) 合起来的最值。

外层 for 循环：先枚举长度 \(len\)，即 \(2^1\) 到 \(2^{\left\lfloor\log n\right\rfloor}\)。

内层 for 循环：枚举起点，即 \(1\) 到 \((n - 2^{len} + 1)\)。

代码：

void build()
{
    for (int i = 1; i <= n; i++) minn[i][0] = read();
    int k = log2(n);
    for (int j = 1; j <= k; j++)
    {
        int R = n - (1 << j) + 1;
        for (int i = 1; i <= R; i++) minn[i][j] = min(minn[i][j-1], minn[i + (1 << (j-1))][j-1]);
    }
}

* 代码中的 log2() 是 cmath 库中的函数。

ST 表查询操作

前面已经提到，给定 \(L\) 与 \(R\)，求 \(\min\limits_{R}^{i=L} a_i\) 的值。

设 \(k = \left\lfloor\log(R-L+1)\right\rfloor\)，其中 \((R-L+1)\) 为区间长度。

这张图很清晰地讲解了 ST 表的查询操作。

那么代码实现就非常容易了。

int query(int L, int R)
{
	int k = log2(R-L+1);
	return min(minn[L][k], minn[R - (1<<k) + 1][k]);
}

ST 表的适用范围与数据结构的对比

在这章开始之前，先扔个完整 ST 表代码：

//结构体外的定义
#define N 100005
int n;
//结构体
struct ST
{
    int minn[N][20];
	void build()
	{
	    for (int i = 1; i <= n; i++) minn[i][0] = read();
	    int k = log2(n);
	    for (int j = 1; j <= k; j++)
	    {
	        int R = n - (1 << j) + 1;
	        for (int i = 1; i <= R; i++) minn[i][j] = min(minn[i][j-1], minn[i + (1 << (j-1))][j-1]);
	    }
	}
	int query(int L, int R)
	{
		int k = log2(R-L+1);
		return min(minn[L][k], minn[R - (1<<k) + 1][k]);
	}
};
ST a;

用结构体封装了，代码很清新吧！

大家观察一下代码，不难发现：

build() 的时间复杂度是 \(O(n \log n)\)。
query() 的时间复杂度是 \(O(1)\)。

我们发现，线段树同样可以解决这类问题。

将线段树拉过来对比一下：

* 前台图炸了，只能在后台截图QwQ

通过表格可以看到，两者各有利弊。

模板题

T1：P1816

求最小。

直接用上文的代码即可。

T2：P3865

求最大。

代码稍微更改一下就好。

T3：P2880

同时维护最大与最小的 ST 表。

查询时作差即可，非常简单。

代码略。

* 如果你真的想学习 ST 表，以上模板题建议从零开始盲打一遍。

结语 & 参考文献

感谢大家看完整篇文章。

大部分内容参考了书籍《算法训练营：进阶篇》。

图片均为自己手绘，图片与文章未经允许不得转载。

首发：2022-05-07 16:35:56

标签：log,minn,int,代码,笔记,ST,学习,dp
From： https://www.cnblogs.com/liangbowen/p/16622859.html

目录