形式化题目

给定长度为 $N$ 的静态数列 $a_1, a_2, \dots, a_N$ 和 $M$ 个询问。每个询问给出闭区间端点 $1 \leqslant A \leqslant B \leqslant N$，要求回答该区间的最大值：

所有询问期间数列不发生修改，即静态区间最大值查询（RMQ）。输入样例数列为 $[34, 1, 8, 123, 3, 2]$，询问 $[1, 5]$ 的答案是 $123$，询问 $[2, 3]$ 的答案是 $8$。

正解

思路

朴素做法与瓶颈。 每次询问从 $A$ 扫到 $B$ 维护最大值，单次 $O(N)$，总代价 $O(NM)$， 最坏 $2 \times 10^5 \times 10^4 = 2 \times 10^9$ 次比较。瓶颈在于不同询问大量覆盖相同子区间， 朴素做法没有复用任何结果；必须预处理，让单次询问降到 $O(1)$。

关键观察：$\max$ 是幂等的。 $\max(S \cup S) = \max(S)$，区间允许重叠地拆成两段再合并。 于是只要备齐"长度为 $2$ 的幂"的区间的最大值，任意长度的区间都能用两块拼出来。

倍增建表。 长度 $2^k$ 的区间恰好由两个长度 $2^{k-1}$ 的区间拼成，因此可以逐层递推：

其中 $st[k][i]$ 表示从 $i$ 开始、长度 $2^k$ 的区间最大值（0-based 下标）。下表是样例数列 $[34, 1, 8, 123, 3, 2]$ 的完整 ST 表，行是层 $k$，列是起点 $i$：

观察点：第 $k$ 行第 $i$ 列由第 $k-1$ 行第 $i$ 列和第 $i + 2^{k-1}$ 列取 max 得到， 例如 $st[2][0] = \max(st[1][0], st[1][2]) = \max(34, 123) = 123$。层数到 $2^k > N$ 为止， 每层比上一层短一半，总规模 $O(N \log N)$。

查询两块覆盖。 对询问 $[A, B]$（换算成 0-based 的 $[l, r]$），令 $len = r - l + 1$、 $k = \lfloor \log_2 len \rfloor$，答案取两块的 max：

因为 $2^k \leqslant len < 2^{k+1}$，每块长度 $2^k \leqslant len$ 所以都落在询问区间内； 两块相交等价于 $l + 2^k - 1 \geqslant r - 2^k + 1$，即 $2^{k+1} \geqslant len + 1$， 由 $len < 2^{k+1}$ 保证，故并集恰好是 $[l, r]$；重叠部分因幂等性不影响答案。用样例验证： 询问 $[1, 5]$（0-based $0..4$，$len = 5$，$k = 2$）取 $st[2][0] = 123$ 与 $st[2][1] = 123$， 两块分别覆盖 $0..3$ 和 $1..4$，并起来恰是 $0..4$，答案 $123$； 询问 $[2, 3]$（0-based $1..2$，$len = 2$，$k = 1$）取 $st[1][1] = 8$，答案 $8$。

查对数与输出。 $\lfloor \log_2 len \rfloor$ 用 len.bit_length() - 1 直接得到， 整数运算，无浮点误差；本题 $M$ 只有 $10^4$，不必像大 $M$ 的题目那样线性预处理 logs 表， 输出先攒进列表最后一次性写出。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:21
# update_at: 2026-09-30 17:21

import sys
from collections.abc import Iterator


def build_st(a: list[int]) -> list[list[int]]:
    """ST 表：st[k][i] = a[i..i+2^k-1] 的最大值，由下一层两个半段合并。"""
    st = [a]
    span = 2  # 当前层区间长度
    while span <= len(a):
        prev = st[-1]
        half = span >> 1
        st.append([max(prev[i], prev[i + half]) for i in range(len(a) - span + 1)])
        span <<= 1
    return st


def query(st: list[list[int]], left: int, right: int) -> int:
    """回答闭区间 [left, right] 的最大值：两块可重叠的 2 的幂区间取 max。"""
    length = right - left + 1
    k = length.bit_length() - 1                      # 不超过区间长度的最大 2 的幂指数
    # 幂等的 max 允许重叠，两块并起来恰好盖住 [left, right]
    return max(st[k][left], st[k][right - (1 << k) + 1])


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    count = next(data)                               # 数字个数 N
    values = [next(data) for _ in range(count)]
    ask_count = next(data)                           # 询问次数 M

    st = build_st(values)

    # 题目按 1-based 给出左右端点，依次减 1 转成 0-based 下标
    out = [str(query(st, next(data) - 1, next(data) - 1)) for _ in range(ask_count)]
    sys.stdout.write('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:19
 * update_at: 2026-10-05 07:19
 */
// main.cpp：静态区间最大值（RMQ），ST 表（倍增）正解。
// 预处理 O(N log N)，每次询问 O(1)，满足 N <= 2e5、M <= 1e4 的规模。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG = 18; // 2^18 > 2e5，层数够用

typedef long long ll;

int n, m;
ll a[MAXN];        // a[i]：第 i 个数（下标从 1 开始，与题面对应）
ll st[LOG][MAXN];  // st[k][i]：从 i 开始、长度为 2^k 的区间的最大值

// 预处理 ST 表：长度 2^k 的区间由两段长度 2^(k-1) 的区间拼成。
// max 有幂等性（重叠不影响结果），所以查询时允许两块区间重叠。
void build_st() {
    for (int i = 1; i <= n; i++) st[0][i] = a[i];
    for (int k = 1; (1 << k) <= n; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
}

// 回答询问 [l, r] 的最大值：取两块长度 2^k 的区间覆盖 [l, r]。
// k = floor(log2(len))，两块起点分别是 l 和 r - 2^k + 1。
ll query_max(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++; // 求 floor(log2(len))，不用浮点
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;

    build_st();

    for (int i = 1; i <= m; i++) {
        int A, B;
        cin >> A >> B;
        cout << query_max(A, B) << "\n";
    }

    return 0;
}

复杂度

• 时间：建表 $O(N \log N)$，查询每条 $O(1)$，合计 $O(N \log N + M)$。
• 空间：$O(N \log N)$ 个表项，$N = 2 \times 10^5$ 时约 $3.6 \times 10^6$ 个整数； 本题 Python 实现实测峰值约 67.7 MB，在 128 MB 限制内。

总结

静态 RMQ 的标准解法是 ST 表：$\max$ 幂等 + 长度按 $2$ 的幂倍增递推，使任意区间都能 用两块可重叠的 $2$ 幂区间覆盖，从而 $O(N \log N)$ 预处理、$O(1)$ 回答每次询问， 恰好匹配本题 $N \leqslant 2 \times 10^5$、$M \leqslant 10^4$ 的规模。