Python ST表实现区间最大值查询

好的，这是一个区间最大值查询问题，我们可以用**线段树**或**ST表**来实现，这里我给出一个使用**ST表**的解法，因为它的查询速度是O(1)，非常适合这种多次查询的场景。 ```python import math n, q = map(int, input().split()) a = list(map(int, input().split())) # 🧱 构建ST表 k = int(math.log2(n)) + 1 st = [[0] * k for _ in range(n)] # 初始化st表，长度1的区间最大值就是本身 for i in range(n): st[i][0] = a[i] # 动态规划构建st表 j = 1 while (1 << j) <= n: i = 0 while i + (1 << j) - 1 < n: st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]) i += 1 j += 1 # 🔍 处理查询 for _ in range(q): L, R = map(int, input().split()) # 因为题目下标从1开始，转换为0-based L -= 1 R -= 1 length = R - L + 1 k = int(math.log2(length)) ans = max(st[L][k], st[R - (1 << k) + 1][k]) print(ans) ``` ### 🧠 思路讲解 1. **设计数据结构**：使用ST表（Sparse Table），它是一种用于解决区间可重复贡献问题（如最大值、最小值、GCD等）的数据结构，支持O(1)查询。 2. **构建ST表**： - `st[i][j]` 表示从下标 `i` 开始，长度为 `2^j` 的区间内的最大值。 - 初始化 `st[i][0] = a[i]`。 - 递推公式：`st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])`。 3. **查询过程**： - 对于区间 `[L, R]`，计算长度 `len = R - L + 1`。 - 找到最大的 `k` 使得 `2^k <= len`。 - 结果 = `max(st[L][k], st[R - 2^k + 1][k])`，即两个长度均为 `2^k` 的区间覆盖整个 `[L, R]`。 ### 💡 开发注意要点 - **下标转换**：输入中的L和R是从1开始的，在代码中要减1变成0-based下标。 - **边界处理**：ST表的构建和查询都要注意数组越界问题，确保索引有效。 - **日志计算**：每次查询都计算一次 `log2`，但ST表本身已经将复杂度降到O(1)，这部分开销可以接受。如果追求极致性能，可以预处理log2值。 - **数据类型**：题目中n<100，ai没有明确范围，但用Python的int可以处理任意整数。 ######[AI问答 | 709点数解答 | 2026-06-21 19:16:23]