1.题目
给定一个长度为 n 的数列和 m 个查询，每个查询指定一个闭区间，要求对每个查询输出该区间内的最小值。
2.思路
其实用Python的话，我们可以直接用Python内置的min函数做，但是这种方法很容易超时，所以我们用ST表优化
3.ST表（Sparse Table）
1. 概述
ST 表是一种高效的静态区间查询数据结构，主要用于解决静态 RMQ（Range Minimum Query，区间最小值查询）和 RMQ 的变种问题。ST 表的优点在于预处理时间为 (O(n \log n))，查询时间为 (O(1))。但是，它不支持动态更新，只适用于静态数据。
2. 基本原理
ST 表利用了倍增思想，将查询范围的长度化为 (2^k) 的形式。任何区间都可以表示为两个重叠的 (2^k) 的区间，这样可以利用预处理的数据快速得到结果。
3. 构建 ST 表
预处理步骤
-
初始化数组：创建一个二维数组
st，其中st[i][j]表示从i开始长度为 (2^j) 的区间的最小值。 -
填充初始值：对于长度为 1 的区间，直接填充原数组的值：
-
递推填充：对于长度为 (2^j) 的区间，通过长度为 (2^{j-1}) 的区间递推得到：
代码实现
import math
def build_st(arr):
# 元素个数
n = len(arr)
# 这里是深度
k = int(math.log2(n)) + 1
# n重循环，最后形成树，当然这里每个都是0
st = [[0] * k for _ in range(n)]
# 初始化长度为 1 的区间
for i in range(n):
# 从i开始的长度为0的，实际上就是自己
st[i][0] = arr[i]
# 递推填充
j = 1
'''
这里一种巧妙的方法，(1 << j) 对于数字1二进制左移j位，相当于增加2的幂次
(1 << 1) 等于 2
(1 << 2) 等于 4
(1 << 3) 等于 8
'''
# 当前的层级小于等于数组元素的总个数（纵向）
while (1 << j) <= n:
i = 0
# 当前层级（横向）
while (i + (1 << j) - 1) < n:
st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])
i += 1
j += 1
return st
这里本质上是一个树形（每次划分都是幂次的）的二维矩阵，构建是ST表，主要是为了查询方便
4. 查询 ST 表
利用 ST 表进行查询时，可以将任意区间 [L, R] 分解为两个重叠的 (2^k) 区间，并利用预处理好的最小值快速得到结果。
查询步骤
-
确定 k 值：计算
-
利用 ST 表查询：查询结果为：
代码实现
def query_st(st, L, R):
j = int(math.log2(R - L + 1))
return min(st[L][j], st[R - (1 << j) + 1][j])
5. 例子
输入
arr = [1, 3, 2, 7, 9, 11, 3, 5, 2, 6]
st = build_st(arr)
查询示例
# 查询区间 [2, 5]
print(query_st(st, 2, 5)) # 输出 2
# 查询区间 [4, 9]
print(query_st(st, 4, 9)) # 输出 2
6. 应用
- RMQ（Range Minimum Query）：快速查询数组某个区间的最小值。
- RMQ 变种：如最大值查询、区间和查询等（通过类似的构建和查询方法实现）。
7. 优缺点
优点
- 查询速度快：预处理后查询时间为 (O(1))。
- 实现简单：基于数组实现，代码简洁明了。
- 适用性广：可用于各种静态区间查询问题。
缺点
- 预处理时间和空间复杂度较高：预处理时间和空间复杂度均为 O(n log n)
- 不支持动态更新：只能处理静态数据，无法处理动态插入、删除和更新操作。
8. 变种
- 最大值查询（Range Maximum Query）：构建 ST 表时取最大值即可。
- 区间和查询（Range Sum Query）：利用 ST 表存储区间和，构建和查询方法类似。
- 其他区间统计：可以根据具体需求调整构建和查询方法。
| 特点 | 数组实现 | 树实现 |
|---|---|---|
| 数据结构 | 简单的数组 | 树 |
| 查找操作 | 直接返回数组值，(O(1)) | 使用路径压缩，接近 (O(1)) |
| 合并操作 | 遍历数组更新代表元，(O(n)) | 按秩合并，接近 (O(1)) |
| 路径压缩 | 无 | 有，减少树的高度 |
| 实现复杂度 | 简单 | 稍微复杂，需要维护树结构 |
| 适用场景 | 小规模数据 | 大规模数据，动态连通性问题 |
总结
- 数组实现：适合于小规模数据集，简单直观，但操作效率较低。
- 树实现：适合于大规模数据集，特别是在需要频繁查找和合并操作时，效率更高。
4. 解决方案
import math
def build_st(arr):
n = len(arr)
k = int(math.log2(n)) + 1
st = [[0] * k for _ in range(n)]
# 初始化长度为 1 的区间
for i in range(n):
st[i][0] = arr[i]
# 递推填充
j = 1
while (1 << j) <= n:
i = 0
while (i + (1 << j) - 1) < n:
st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])
i += 1
j += 1
return st
def query_st(st, L, R):
j = int(math.log2(R - L + 1))
return min(st[L][j], st[R - (1 << j) + 1][j])
def solve(n, m, arr, queries):
# 构建 ST 表
st = build_st(arr)
# 处理查询
results = []
for L, R in queries:
results.append(query_st(st, L, R))
return results
# 输入处理
def main():
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
m = int(data[1])
arr = list(map(int, data[2:n+2]))
queries = []
for i in range(m):
L = int(data[n+2 + 2*i]) - 1 # 转换为0索引
R = int(data[n+2 + 2*i + 1]) - 1 # 转换为0索引
queries.append((L, R))
# 计算并输出结果
results = solve(n, m, arr, queries)
for result in results:
print(result)
if __name__ == "__main__":
main()
主要是构建开销大，查询的话倒是比较方便
