C++区间最大值查询（RMQ）暴力与ST表解法对比

这个问题是一个典型的 **区间最大值查询（Range Maximum Query, RMQ）** 问题。 由于 `n < 100`，用最简单的 **暴力遍历** 即可在每次查询中直接用循环找最大值。 但为了扩展性和展示算法思想，这里我给出两种解法： --- ## ✅ 解法一：暴力法（适合本题数据范围） 直接对每个查询的区间 `[L, R]` 遍历得到最大值。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> a(n + 1); // 下标从1开始 for (int i = 1; i <= n; i++) { cin >> a[i]; } while (q--) { int L, R; cin >> L >> R; int max_val = a[L]; for (int i = L + 1; i <= R; i++) { if (a[i] > max_val) { max_val = a[i]; } } cout << max_val << endl; } return 0; } ``` **时间复杂度：** - 每轮查询 O(n)，总复杂度 O(q * n)。 - 由于 n < 100，q 即使很大也完全能过。 --- ## ✅ 解法二：ST表（Sparse Table，适合多次查询，O(1) 回答） 如果希望拓展到更大的 n（比如 10^5），可以使用 ST 表预处理，然后每次查询 O(1) 回答。 ```cpp #include <iostream> #include <cmath> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } // 构建 ST 表 int k = log2(n) + 1; vector<vector<int>> st(n + 1, vector<int>(k)); for (int i = 1; i <= n; i++) { st[i][0] = a[i]; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } // 回答查询 while (q--) { int L, R; cin >> L >> R; int len = R - L + 1; int j = log2(len); int ans = max(st[L][j], st[R - (1 << j) + 1][j]); cout << ans << "\n"; } return 0; } ``` **时间复杂度：** - 预处理 O(n log n) - 每次查询 O(1) - 适合大数据量多次查询的场景。 --- ## 🧠 关键开发注意点 - 下标处理：输入中 L、R 是从 **1 开始** 的，数组也要从 1 开始存。 - 对于暴力法：每次循环起始设为 a[L]，避免多一个赋值。 - 对于 ST表：注意 `log2` 使用 `cmath` 库，并且 `R - (1<<j) + 1` 要保证不越界。 - 输入输出优化：大数据量时使用 `ios::sync_with_stdio(false); cin.tie(nullptr);` 加速。 ######[AI问答 | 839点数解答 | 2026-06-06 14:20:19]