忠诚 - 题目列表

题意

给定一个不再修改的数组，多次询问闭区间 [left, right] 内的最小值。

思路

table[level][i] 保存从 i 开始、长度为 $2^{level}$ 的区间最小值。相邻两块长度 $2^{level-1}$ 的区间合并即可得到下一层。

查询长度为 length 的区间时，令 level = floor(log2(length))。取查询区间最左和最右的两个长度 $2^{level}$ 的块；它们可能重叠，但 min 重复计算元素不会改变结果。

Python 知识

array("i") 比 Python 整数列表紧凑，适合保存 $O(n\log n)$ 个 ST 表值。
logs[i] = logs[i // 2] + 1 可线性预处理所有整数对数。
生成器表达式直接交给 array，避免先创建中间列表。
print(*answers) 自动按空格输出所有询问答案。

代码

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
26import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
n, queries = next(data), next(data)
values = array("i", (next(data) for _ in range(n)))
logs = [0] * (n + 1)
for i in range(2, n + 1):
    logs[i] = logs[i // 2] + 1

table = [values]
level = 1
while 1 << level <= n:
    half = 1 << (level - 1)
    previous = table[-1]
    table.append(array("i", (min(previous[i], previous[i + half])
                             for i in range(n - (1 << level) + 1))))
    level += 1

answers = []
for _ in range(queries):
    left, right = next(data) - 1, next(data) - 1
    level = logs[right - left + 1]
    answers.append(str(min(table[level][left], table[level][right - (1 << level) + 1])))
print(*answers)

原有 C++ 版本保留如下：

cpp

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
71
72
73
74
75#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 100005;
const int LOGN = 20; // 2^17 > 100000，开到 20 足够了

// f[i][j] 表示从 i 开始，长度为 2^j 的区间最小值
int f[MAXN][LOGN];
// Log[i] 存储 i 的以 2 为底的对数 (向下取整)
int Log[MAXN]; 
int n, m;

void init() {
    // 1. 预处理 Log 数组
    // Log[1] = 0, Log[2]=1, Log[3]=1, Log[4]=2 ...
    Log[1] = 0;
    for (int i = 2; i <= m; i++) {
        Log[i] = Log[i / 2] + 1;
    }

    // 2. 初始化 ST 表的第一列 (长度为 2^0 = 1 的区间)
    // 这一步在输入时已经完成了，即 f[i][0] = input[i]

    // 3. 动态规划填表
    // j 是长度指数，必须在外层循环
    for (int j = 1; j <= LOGN - 1; j++) {
        // i 是起点
        // 注意边界：i + 2^j - 1 不能超过 m
        for (int i = 1; i + (1 << j) - 1 <= m; i++) {
            // 状态转移：左半部分 和 右半部分 取 min
            // 右半部分的起点是 i + 2^(j-1)
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = Log[len]; // 找到最大的 k 使得 2^k <= len
    
    // 覆盖左边 [l, l + 2^k - 1] 和 右边 [r - 2^k + 1, r]
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 题目中输入是 m, n
    // m 是账目数量(数组大小), n 是询问次数
    cin >> m >> n;

    for (int i = 1; i <= m; i++) {
        cin >> f[i][0]; // 读入数据直接存入 ST 表的第 0 层
    }

    // 构建 ST 表
    init();

    // 处理询问
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << " ";
    }
    cout << endl;

    return 0;
}

复杂度

预处理时间与空间均为 $O(n\log n)$ ，每次询问 $O(1)$ 。

总结

数组静态、询问很多、运算允许区间重叠时，ST 表是比线段树更直接的选择。

忠诚

目录

题意

思路

Python 知识

代码

复杂度

总结