求优化：多区间数字统计的O(n*m)复杂度代码改进方案

嘿，我太懂你现在的困扰了——当n和m的规模稍微大一点，比如到1e4或者更高时，你写的O(n*m)双重循环肯定会超时，毕竟每次查询都要遍历所有数字，实在太浪费时间了。这里给你两种高效的优化思路，能把时间复杂度直接降到O(n log n + m log n)，完美解决性能问题！

方案一：排序 + 二分查找（最简单直接） #

这个方法的核心思路是：先把数字数组排序，然后利用二分查找快速定位每个区间的边界，直接算出区间内的数字数量。

修改后的代码 #

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
    int n,m,temp,temp1;
    vector<pair<int, int>> uogienes;
    vector<int> erskeciai;
    cin >> n >> m;
    for (int i = 0; i< n; i++){
        cin>>temp;
        erskeciai.push_back(temp);
    }
    for (int i = 0; i<m; i++){
        cin>> temp >> temp1;
        uogienes.push_back(make_pair(temp, temp1));
    }

    // 关键优化部分
    sort(erskeciai.begin(), erskeciai.end());
    for(int i = 0; i<m; i++){
        int L = uogienes[i].first;
        int R = uogienes[i].second;
        // 找到第一个 >= L 的元素位置
        auto left = lower_bound(erskeciai.begin(), erskeciai.end(), L);
        // 找到第一个 > R 的元素位置
        auto right = upper_bound(erskeciai.begin(), erskeciai.end(), R);
        // 两个迭代器的距离就是区间内的数字数量
        cout << (right - left) << "\n";
    }
    return 0;
}

为什么这能提速？ #

• 排序只需要一次，时间是O(n log n)
• 每个查询用两次二分查找，每次二分是O(log n)，m个查询就是O(m log n)
• 总复杂度是O(n log n + m log n)，对比原来的O(n*m)，当n和m都是1e5时，原来的代码要跑1e10次操作，而优化后只需要约4e6次操作，差距巨大！

方案二：离散化 + 前缀和（适合复杂场景） #

如果你的数字范围特别大（比如达到1e9），或者需要频繁进行这类区间查询，离散化+前缀和的方法会更灵活。它的核心是把所有用到的数值（数字和区间端点）映射到一个紧凑的下标范围，再用前缀和快速统计。

修改后的代码 #

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
    int n,m,temp,temp1;
    vector<pair<int, int>> uogienes;
    vector<int> erskeciai;
    cin >> n >> m;
    for (int i = 0; i< n; i++){
        cin>>temp;
        erskeciai.push_back(temp);
    }
    for (int i = 0; i<m; i++){
        cin>> temp >> temp1;
        uogienes.push_back(make_pair(temp, temp1));
    }

    // 关键优化部分：离散化+前缀和
    vector<int> all_values;
    // 收集所有需要用到的数值（数字和查询的左右端点）
    for(int x : erskeciai) all_values.push_back(x);
    for(auto &p : uogienes) {
        all_values.push_back(p.first);
        all_values.push_back(p.second);
    }
    // 排序并去重，得到离散化后的映射表
    sort(all_values.begin(), all_values.end());
    all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());

    // 统计每个离散值的出现次数
    vector<int> cnt(all_values.size(), 0);
    for(int x : erskeciai) {
        int idx = lower_bound(all_values.begin(), all_values.end(), x) - all_values.begin();
        cnt[idx]++;
    }

    // 构建前缀和数组
    vector<int> prefix(all_values.size() + 1, 0);
    for(int i = 0; i < all_values.size(); i++) {
        prefix[i+1] = prefix[i] + cnt[i];
    }

    // 处理每个查询
    for(auto &p : uogienes) {
        int L = p.first;
        int R = p.second;
        int left = lower_bound(all_values.begin(), all_values.end(), L) - all_values.begin();
        int right = upper_bound(all_values.begin(), all_values.end(), R) - all_values.begin();
        cout << prefix[right] - prefix[left] << "\n";
    }
    return 0;
}

这个方案的优势 #

• 即使数字范围极大，也能通过离散化把空间压缩到O(n+m)级别
• 前缀和预处理完成后，每次查询的时间还是O(log(n+m))，后续新增查询也能快速处理
• 复杂度和方案一差不多，但扩展性更强，比如如果需要支持动态添加数字，还能在此基础上扩展成树状数组或线段树

内容的提问来源于stack exchange，提问作者Mike Leedlow