【CSP-S】数据结构 ST 表详解

作者要备战 Csp-s 比赛，大家可以查看相关的专栏 传送门

ST表可以干什么

ST 表主要用于求解静态区间 RMQ 问题，静态区间 RMQ 问题就是给你一个数组，然后给你几个区间，计算区间和，区间最大值，区间最小值等问题

ST 表的优势

ST 表可以快速查询区间 RMQ 问题。需要一个 $O(n\log n)$ 的预处理，但是单次查询只要 $O(1)$ ，对于线段树和树状数组这两个数据结构的查询 $O(\log n)$ 他会更快!

其次 ST 表编程简单，代码量相对于 线段树和树状数组 更 简单 而且常数更小

ST 表的劣势

ST 表只可以求解静态 RMQ 问题，不支持修改操作。而且 ST 表只支持可重复性运算(这个后面会讲到)

ST 表的实现原理

Step1: 预处理

ST 表主要是基于倍增的思想进行预处理。

定义

我们设 $dp[start][size]$ 表示从 $start$ 开始，
区间长度为 $2^{size}$ 的答案。

实现

那么我们怎么处理这个 $dp$ 数组呢？我们考虑使用倍增的方法实现
公式
$$dp[start][size]=dp[start][size-1]+dp[start+2^{size-1}][size-1]$$

下面进行一些推导
当前的区间 $dp[start][size]$ 可以看成两个区间的合并而成。

---

第一个区间：$dp[start][size-1]$
从 $start$ 位置开始，长度为 $2^{size-1}$ 的区间

---

第二个区间: $dp[start+2^{size-1}][size-1]$
从 $start+2^{size-1}$ 开始，长度为 $2^{size-1}$

---

其实很简单的一个道理
长度为 $2^{size}$ 的区间一定会由两个长度为 $2^{size-1}$ 的区间合并得到。

因为 $2^{size-1}+2^{size-1}=2^{size}$
如果还是不懂，我们可以证明一下 $2^{x-1}+2^{x-1}=2^x$
证明:
$$左边=2^{x-1}+2^{x-1}=2^{x-1}\times 2=2^x$$

只是将第二个区间起点的位置变化成了第一个区间起点 + 第一个区间长度而已。

代码

for (int size = 1; size <= Log2[n]; size++) // Log2[i] 表示 log2(i) 是多少for (int start = 1; start + (1 << size) <= n; start++) // 枚举开始位置ST[start][size] = max(ST[start][size - 1], ST[start + (1 << (size - 1))][size - 1]);

Step2: 查询

这里我们要考虑如何查询。
首先我们发现一个观点，任何一个区间都可以化成两个长度为 $2^i$ 的区间相加

比如区间 $[5,11]$ 可以化为 $[5,8]$(长度为 $4$ 即 $2^2$) 和 $[8,11]$(长度为 $4$ 即 $2^2$)

但是我们会发现，这里面会有一些元素计算过两次！比如 $8$，所以 ST 表只可以计算 区间最大值，区间最小值 因为一个数就算比较很多遍不影响最大最小值 但是 ST 表不可以计算区间和 因为会有元素计算了 $2$ 次

所以我们可以正着查询一次，然后倒着查询一次即可

什么意思?
就是指我们查询当前的左边界可以延伸到的最长位置(不超过右边界)
然后我们再次查询当前的右边界可以向左延伸的最长位置(不超过左边界)
两个答案相加即为最终的答案

注意区间是从左到右的，在进行步骤 2 时要减去区间长度

代码

int s = Log2[r - l + 1];
printf("%d\n", max(ST[l][s], ST[r - (1 << s) + 1][s]));

例题 区间最大值问题

题目位置：https://www.luogu.com.cn/problem/P3865
代码:

#include <stdio.h>
#include <ctype.h>//#define getchar getchar
//int isdigit(char x) {return ((x) >= '0' && (x) <= '9');}int read() {int ret = 0;char ch;while (!isdigit(ch = getchar()));do {ret = ret * 10 + ch - '0';} while (isdigit(ch = getchar()));return ret;
}#define N ((int) 1e5 + 10)
int Log2[N];
int n, m;void InitLog2(void)
{Log2[1] = 0; // 2^0 = 1for (int i = 2; i <= n + 1; i++) Log2[i] = Log2[i / 2] + 1;
}
int max(int a, int b) {return a > b ? a : b;}int ST[N][18];
int arr[N];void InitSt(void)
{for (int i = 1; i <= n; i++) ST[i][0] = arr[i]; // 区间长度为 1for (int size = 1; size <= Log2[n]; size++)for (int start = 1; start + (1 << size) <= n; start++) // 枚举开始位置ST[start][size] = max(ST[start][size - 1], ST[start + (1 << (size - 1))][size - 1]);
}int main()
{n = read(), m = read();
//    n = read();for (int i = 1; i <= n; i ++) arr[i] = read();InitLog2(), InitSt();while (m--) {int l = read(), r = read();int s = Log2[r - l + 1];printf("%d\n", max(ST[l][s], ST[r - (1 << s) + 1][s]));}return 0;
}