大规模查询场景下数组区间最大值求解的时间复杂度优化方案咨询

当然可以！你的暴力解法在小规模数据场景下没问题，但当数组和查询量都达到1e6级别时，O(q*(r-l))的时间复杂度肯定会超时——最坏情况下每次查询都要遍历整个数组，总运算量会突破1e12级别，这完全超出了程序的时间承受范围。

针对这种多次静态区间最大值查询的场景，我们有两种高效的预处理方案，能把查询效率大幅提升：

1. 稀疏表（Sparse Table）：静态数组的最优选择 #

稀疏表是专门为无修改操作的静态数组设计的区间查询优化方案，它的预处理时间为O(n log n)，之后每次查询都能做到O(1)时间，完美适配你大量查询的需求。

核心原理 #

我们预处理一个二维数组st，其中st[k][i]代表从索引i开始、长度为2^k的区间内的最大值：

• 初始化：st[0][i] = v[i]（每个长度为1的区间最大值就是元素本身）
• 递推构建：对于每个k >= 1，st[k][i] = max(st[k-1][i], st[k-1][i + 2^(k-1)])（把长度为2^{k的区间拆成两个长度为2}(k-1)的子区间，取两者的最大值）

查询区间[l, r]时：

1. 计算区间长度len = r - l + 1
2. 取k = floor(log2(len))（即最大的k值，使得2^k ≤ len）
3. 区间最大值为max(st[k][l], st[k][r - 2^k + 1])（两个长度为2^k的子区间刚好覆盖整个查询区间）

C++ 实现代码 #

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

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

    const int MAXN = 1e6;
    const int LOG = 20; // 2^20 > 1e6，足够覆盖数组长度

    vector<int> v(MAXN);
    for (auto &i : v) cin >> i;

    // 构建稀疏表
    vector<vector<int>> st(LOG, vector<int>(MAXN));
    for (int i = 0; i < MAXN; ++i) st[0][i] = v[i];
    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i + (1 << k) <= MAXN; ++i) {
            st[k][i] = max(st[k-1][i], st[k-1][i + (1 << (k-1))]);
        }
    }

    int number_of_queries = 1e6;
    while (number_of_queries--) {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        int k = __lg(len); // GCC内置函数，返回log2(len)的整数部分
        int ans = max(st[k][l], st[k][r - (1 << k) + 1]);
        cout << ans << '\n';
    }

    return 0;
}

注意事项 #

• 加入ios::sync_with_stdio(false); cin.tie(nullptr);加速输入输出，否则1e6级别的IO操作会超时
• 如果使用非GCC编译器，可以用static_cast<int>(log2(len))替代__lg，或者预计算log数组避免重复计算

2. 线段树（Segment Tree）：支持动态修改的通用方案 #

如果之后你的需求扩展为需要修改数组元素，线段树会是更合适的选择。它的预处理时间为O(n)，每次查询和修改的时间都是O(log n)，虽然查询速度略慢于稀疏表，但灵活性更高。

核心原理 #

线段树是一种二叉树结构，每个节点对应数组的一个区间：

• 叶子节点对应数组的单个元素
• 非叶子节点存储其左右子节点区间的最大值

查询区间[l, r]时，我们递归地将查询区间拆分为线段树中已有的区间，合并这些区间的最大值得到最终结果。

C++ 核心实现示例 #

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

const int MAXN = 1e6;
vector<int> tree(4 * MAXN); // 线段树通常开数组大小的4倍空间
vector<int> v(MAXN);

void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = v[start];
    } else {
        int mid = (start + end) / 2;
        build(2*node, start, mid);
        build(2*node+1, mid+1, end);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0; // 数组全为正整数，返回0不影响最大值计算
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    int left_max = query(2*node, start, mid, l, r);
    int right_max = query(2*node+1, mid+1, end, l, r);
    return max(left_max, right_max);
}

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

    for (auto &i : v) cin >> i;
    build(1, 0, MAXN-1);

    int number_of_queries = 1e6;
    while (number_of_queries--) {
        int l, r;
        cin >> l >> r;
        cout << query(1, 0, MAXN-1, l, r) << '\n';
    }

    return 0;
}

方案选择建议 #

• 如果数组是静态的（无需修改），优先选择稀疏表，查询速度更快，实现也相对简单
• 如果需要动态修改数组元素，选择线段树，它能同时支持高效的查询和修改操作

这两种方案的总时间复杂度都能控制在O(n log n + q)或O(n + q log n)，完全可以处理1e6级别的数组和查询量。

内容的提问来源于stack exchange，提问作者Ahmed Mohammed