NOI 竞赛模拟题：P3865 【模板】ST 表

题目描述

给定一个长度为 $N$ 的序列 $A$，以及 $M$ 次询问。每次询问给定一个区间 $[L, R]$，请输出该区间内的最大值。

要求：

1. 预处理时间复杂度：$O(N \log N)$。
2. 单次查询时间复杂度：$O(1)$。
3. 空间复杂度：$O(N \log N)$。

在 NOI 竞赛中，本题是解决 RMQ（Range Minimum/Maximum Query，区间最值询问） 问题的经典模板。由于查询次数 $M$ 较大，必须严格保证查询的 $O(1)$ 效率。

---

输入格式

第一行包含两个整数 $N, M$，分别表示序列长度和询问次数。 第二行包含 $N$ 个整数，表示初始序列 $A$。 接下来 $M$ 行，每行包含两个整数 $L_i, R_i$，表示询问的区间。

输出格式

输出共 $M$ 行，每行包含一个整数，对应每次询问的结果。

---

输入输出样例

样例 1

输入：

8 8
3 2 4 5 6 8 1 2
1 2
8 8
1 7
4 6
7 8
2 4
1 3
2 6

输出：

3
8
8
8
2
5
4
8

---

数据范围与提示

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^6$
• $1 \le A_i \le 10^9$
• $1 \le L_i \le R_i \le N$
• 注意：由于询问量巨大，建议使用快速读入（Fast I/O）技术。

---

1. 预备知识点

• 倍增思想（Binary Lifting）：通过 2 的幂次（$1, 2, 4, 8 \dots$）来覆盖区间。
• 动态规划（DP）：ST 表的构建本质是一个 DP 过程。
• 区间重叠性（Idempotency）：区间最大值满足 $\max(x, x) = x$，即重叠覆盖不影响结果。
• 位运算：使用 (1 << j) 表示 $2^j$，__builtin_log2 或预处理 log 数组。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：状态定义

我们定义 $f[i][j]$ 表示：以第 $i$ 个数开始，长度为 $2^j$ 的区间内的最大值。 即范围为 $[i, i + 2^j - 1]$。

第二步：转移方程

如何求 $f[i][j]$？我们可以将其平分为两半：

• 左半部分：长度为 $2^{j-1}$，即 $f[i][j-1]$。
• 右半部分：长度为 $2^{j-1}$，起始点为 $i + 2^{j-1}$，即 $f[i + 2^{j-1}][j-1]$。
• 方程：f[i][j] = max(f[i][j-1], f[i + 2^{j-1}][j-1])。

第三步：查询逻辑

对于区间 $[L, R]$，长度 $len = R - L + 1$。 我们需要找到一个最大的 $k$，使得 $2^k \le len$。 这时，区间 $[L, R]$ 可以被两个长度为 $2^k$ 的小区间完全覆盖：

1. 从 $L$ 开始往后 $2^k$ 个数：$f[L][k]$。
2. 从 $R$ 开始往前 $2^k$ 个数：$f[R - 2^k + 1][k]$。 由于 $\max$ 操作允许重叠，这两个块的最大值即为答案。

第四步：复杂度分析与优化

• 时间：预处理 $O(N \log N)$，查询 $O(1)$。
• 常数优化：cmath 的 log2() 函数较慢，建议通过递推预处理 log 数组：log[i] = log[i/2] + 1。

---

3. 算法逻辑流程图 (Mermaid)

预处理部分 (Build)

graph TD
    A["开始: 读入 N, M"] --> B["循环 i 从 1 到 N"]
    B --> C["读入 A_i, 初始化 f_i_0 等于 A_i"]
    C --> D["预处理 log2 数组 (递推实现)"]
    D --> E["外层循环 j 从 1 到 20 (即 log N)"]
    E --> F["内层循环 i 从 1 到 N 减去 2的j次方 加上 1"]
    F --> G["f_i_j = max( f_i_j-1 , f_i_plus_2pow_j-1_j-1 )"]
    G --> F
    F -- "内层结束" --> E
    E -- "预处理完成" --> H["进入查询阶段"]

查询部分 (Query)

graph TD
    I["开始查询 L, R"] --> J["计算区间长度 len = R - L + 1"]
    J --> K["获取预处理的 k = log_len"]
    K --> L["计算 max_val = max( f_L_k, f_R_minus_2powk_plus_1_k )"]
    L --> M["输出结果, 处理下一个询问"]

---

4. 读题关键词与坑点总结

1. “$O(1)$ 查询”：看到 RMQ 且查询次数极多（$2 \times 10^6$），必须直接联想到 ST 表，线段树的 $O(\log N)$ 会超时。
2. “重叠覆盖”：理解为什么 $2^k$ 块可以重叠。这决定了 ST 表不能用于求区间和（Sum），只能用于最值（Max/Min）、最大公约数（GCD）等满足幂等律的操作。
3. “空间开销”：$N=10^5$，$\log N \approx 17$。$10^5 \times 18 \times 4$ 字节 $\approx 7.2$ MB，远小于 NOI 的 128MB/256MB 限制。
4. “读写效率”：在 NOI 比赛中，处理 $10^6$ 级别的数据，cin/cout 即使加了 sync_with_stdio(0) 也可能不够快，首选 scanf/printf 或自定义 getchar 快读。

---

5. 复杂度分析思考过程

• 时间复杂度：
  • 预处理：两层循环，$N \times \log N$。
  • 查询：简单的位移和数组索引，$O(1)$。
  • 总时间：$O(N \log N + M)$。
• 空间复杂度：
  • $f[N][\log N]$ 数组：$O(N \log N)$。
• 优化建议：
  • 若内存极度受限且数据随机，可考虑分块。但在标准 NOI 模板中，ST 表是权衡时间与编程复杂度的最优解。