形式化题目

给定长度为 $N$ 的静态数列 $h_1, h_2, \dots, h_N$ 和 $Q$ 个询问。每个询问给出闭区间端点 $1 \leqslant A \leqslant B \leqslant N$，要求回答该区间的极差：

询问期间数列不发生修改，即静态区间极差查询（RMQ 的极差形式）。

样例数列 $[1, 7, 3, 4, 2, 5]$：询问 $[1, 5]$ 中最高 $7$、最低 $1$，答案 $6$； 询问 $[4, 6]$ 对应子列 $[4, 2, 5]$，答案 $5 - 2 = 3$；询问 $[2, 2]$ 只有一头牛， 答案 $0$。

正解

思路

朴素做法与瓶颈。 每次询问从 $A$ 扫到 $B$ 维护最高、最低身高，单次 $O(N)$， 总代价 $O(NQ)$，最坏 $5\times10^4 \times 1.8\times10^5 = 9\times10^9$ 次比较，必然超时。 瓶颈在于 $Q \gg N$：不同询问大量覆盖相同子区间，朴素做法没有复用任何结果； 必须把单次询问压到 $O(1)$，让「区间极值」变成查表问题。

关键观察：$\max$、$\min$ 都是幂等的。 $\max(S \cup S) = \max(S)$，所以区间允许 重叠地拆成两段再合并（求和则不行，会重复计数）。于是不必预处理全部 $O(N^2)$ 个区间， 只要备齐「长度为 $2$ 的幂」的区间极值，任意区间都能用两段拼出来。

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

其中 $st[k][i]$ 表示从 $i$ 开始、长度 $2^k$ 的区间极值（0-based 下标）；把 $\max$ 换成 $\min$ 即得最小值表。下表是样例数列的两张表，前 3 行是最大值表、后 3 行是最小值表， 行是幂层，列是起点 $i$：

观察点：每层由上一层相隔 $2^{k-1}$ 的两格 pick 得到，例如 $st[2][0] = \max(st[1][0],\ st[1][2]) = \max(7, 4) = 7$。层数到 $2^k > N$ 为止， 每层比上一层短一半，总规模 $O(N \log N)$。

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

因为 $2^k \leqslant len$，两块都落在 $[l, r]$ 内；两块相交由 $len < 2^{k+1}$（$k$ 的定义）保证， 且左块起点是 $l$、右块终点是 $r$，故并集恰为 $[l, r]$；重叠部分因幂等性不影响极值。 用样例验证：询问 $[1, 5]$（0-based $0..4$，$len = 5$，$k = 2$）取两表的 $i=0$、$i=1$ 两格， 最大值 $\max(7, 7) = 7$、最小值 $\min(1, 2) = 1$，答案 $6$； 询问 $[4, 6]$（$len = 3$，$k = 1$）得 $\max(4, 5) - \min(2, 2) = 3$； 询问 $[2, 2]$（$len = 1$，$k = 0$）两格相同，答案 $0$——与样例输出一致。

查对数与查表。 $\lfloor \log_2 len \rfloor$ 用 length.bit_length() - 1 直接得到， 不做浮点运算；询问较多时输出先攒进列表最后一次性写出。

代码

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
47
48
49#!/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:19
# update_at: 2026-09-30 17:19

import sys
from collections.abc import Callable


def build(heights: list[int], pick: Callable[[int, int], int]) -> list[list[int]]:
    """稀疏表：st[j][i] = 区间 [i, i+2^j-1] 的极值，pick 决定取最大还是最小。"""
    size = len(heights)
    st = [heights]
    j = 1
    while (1 << j) <= size:
        prev = st[-1]
        # 两个半长 2^(j-1) 的相邻区间合并成长度 2^j 的区间
        st.append([pick(prev[i], prev[i + (1 << (j - 1))]) for i in range(size - (1 << j) + 1)])
        j += 1
    return st


def range_gap(st_max: list[list[int]], st_min: list[list[int]], left: int, right: int) -> int:
    """闭区间 [left, right] 内最高与最低身高之差。"""
    length = right - left + 1
    j = length.bit_length() - 1  # 2^j <= length < 2^(j+1)
    tail = right - (1 << j) + 1  # 两段 2^j 覆盖整个区间，允许重叠
    return max(st_max[j][left], st_max[j][tail]) - min(st_min[j][left], st_min[j][tail])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, q = next(data), next(data)
    heights = [next(data) for _ in range(n)]  # 每行一头牛的身高
    st_max = build(heights, max)
    st_min = build(heights, min)

    out: list[str] = []
    for _ in range(q):
        left, right = next(data) - 1, next(data) - 1  # 题目 1-indexed → 0-indexed
        out.append(str(range_gap(st_max, st_min, left, right)))

    print('\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
60
61
62
63
64
65
66
67
68
69
70/**
 * 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:27
 * update_at: 2026-10-05 07:27
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;   // 牛的数量上限 5*10^4
const int MAXLOG = 17;    // 2^16 <= 5*10^4 < 2^17，所以只需 0..16 层

typedef long long ll;

ll n, q;

// 身高最大 10^6，区间极值用 int 存即可，省一半内存
int st_max[MAXLOG][MAXN]; // st_max[k][i]：区间 [i, i+2^k-1] 内的最高身高
int st_min[MAXLOG][MAXN]; // st_min[k][i]：区间 [i, i+2^k-1] 内的最低身高
int lg[MAXN];             // lg[len] = floor(log2(len))

// 倍增建表：长度 2^k 的区间由两个长度 2^(k-1) 的区间拼成。
void build_st() {
    lg[1] = 0;
    for (ll i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1;
    }

    for (ll k = 1; (1LL << k) <= n; k++) {
        ll half = 1LL << (k - 1);
        ll cnt = n - (1LL << k) + 1; // 该层能作为起点的个数
        for (ll i = 1; i <= cnt; i++) {
            st_max[k][i] = max(st_max[k - 1][i], st_max[k - 1][i + half]);
            st_min[k][i] = min(st_min[k - 1][i], st_min[k - 1][i + half]);
        }
    }
}

void solve() {
    cin >> n >> q;

    for (ll i = 1; i <= n; i++) {
        cin >> st_max[0][i];
        st_min[0][i] = st_max[0][i];
    }

    build_st();

    for (ll t = 1; t <= q; t++) {
        ll a, b;
        cin >> a >> b;
        ll len = b - a + 1;
        ll k = lg[len];
        // 两段长度为 2^k 的可重叠区间恰好盖住 [a, b]
        ll tail = b - (1LL << k) + 1;
        int hi = max(st_max[k][a], st_max[k][tail]);
        int lo = min(st_min[k][a], st_min[k][tail]);
        cout << hi - lo << '\n';
    }
}

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

    solve();

    return 0;
}

复杂度

• 时间：建两张表各 $O(N \log N)$，每条询问 $O(1)$，合计 $O(N \log N + Q)$， 与 C++ 正解（ST 表）同阶；对比朴素 $O(NQ) = 9\times10^9$。
• 空间：两张表共 $O(N \log N)$ 个表项，$N = 5\times10^4$ 时约 $1.6\times10^6$ 个整数； Python 实现实测峰值 59.6 MB，官方 9 组数据全部正确（本地 0.018–0.160 s，题面限时 1000 ms）。

总结

静态区间极差 = 两次静态 RMQ。ST 表利用 $\max/\min$ 的幂等性，把区间按 $2$ 的幂 可重叠地分成两块，$O(N \log N)$ 预处理、$O(1)$ 回答每次询问，恰好匹配本题 $N \leqslant 5\times10^4$、$Q \leqslant 1.8\times10^5$ 且数组不修改的规模； 若数组带修改，则应改用线段树。