数组区间数字频次统计优化：大数组下内存过高问题求助

你当前代码的问题出在每个前缀位置都保存了一个完整的map<int,int>副本。对于10^{5规模的数组，相当于存了10}5个独立的哈希表，内存开销是O(n*k)（k是数组中不同元素的数量），这种冗余存储直接导致内存爆炸。

根据你的查询场景（在线/离线、查询次数多少），给你三种实用的优化方向：

方案一：离线查询 + 莫队算法（适合查询次数多的场景） #

莫队算法通过对所有查询区间排序，用双指针动态维护当前区间的数字计数，避免了冗余存储。时间复杂度接近O((n+m)√n)，内存仅需O(n+m)，完全适配10^5规模的数组。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN], cnt[MAXN];
struct Query {
    int l, r, idx;
};
int block_size;

// 莫队排序规则，加奇偶优化减少指针移动次数
bool cmp(const Query& x, const Query& y) {
    if (x.l / block_size != y.l / block_size) {
        return x.l < y.l;
    }
    return (x.l / block_size % 2) ? (x.r > y.r) : (x.r < y.r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    block_size = sqrt(n);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<Query> queries(m);
    for (int i = 0; i < m; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end(), cmp);
    
    int cur_l = 1, cur_r = 0;
    for (auto& q : queries) {
        // 调整双指针到当前查询区间
        while (cur_l > q.l) cnt[a[--cur_l]]++;
        while (cur_r < q.r) cnt[a[++cur_r]]++;
        while (cur_l < q.l) cnt[a[cur_l++]]--;
        while (cur_r > q.r) cnt[a[cur_r--]]--;
        
        // 输出当前查询结果
        cout << "Query " << q.idx + 1 << ":\n";
        // 如果元素数值范围大，先做离散化再用数组存cnt
        for (int num = 1; num < MAXN; num++) {
            if (cnt[num] > 0) {
                cout << num << ": " << cnt[num] << '\n';
            }
        }
        cout << '\n';
    }
    return 0;
}

如果数组元素数值过大（超过1e5），先对元素做离散化处理，把数值映射到1~k（k为不同元素数量），再用数组存储计数即可。

方案二：前缀数组+离散化（适合元素可离散化、查询次数少的场景） #

如果数组元素可以离散化，我们为每个离散后的数值维护一个前缀和数组。查询时直接用前缀[r][x] - 前缀[l-1][x]得到x在区间内的出现次数，内存开销仅为O(n + k)，远低于原代码。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<int> a = {1, 2, 2, 3, 4, 5, 5, 5, 6, 7};
    int n = a.size();
    
    // 第一步：离散化数组元素
    vector<int> sorted_unique = a;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()), sorted_unique.end());
    map<int, int> num_to_idx;
    for (int i = 0; i < sorted_unique.size(); i++) {
        num_to_idx[sorted_unique[i]] = i;
    }
    int k = sorted_unique.size();
    
    // 第二步：构建前缀和数组
    vector<vector<int>> prefix(n + 1, vector<int>(k, 0));
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1];
        int idx = num_to_idx[a[i - 1]]; // 原数组是0基，对应前缀数组的1基索引
        prefix[i][idx]++;
    }
    
    // 查询区间[1,4]（对应原数组的第1到第4个元素）
    int l = 1, r = 4;
    cout << "Query result:\n";
    for (int i = 0; i < k; i++) {
        int count = prefix[r][i] - prefix[l - 1][i];
        if (count > 0) {
            cout << sorted_unique[i] << ": " << count << '\n';
        }
    }
    return 0;
}

方案三：在线查询+主席树（适合必须在线处理的场景） #

如果你的需求是必须在线处理查询（不能提前收集所有查询排序），可以用可持久化线段树（主席树）。每个版本的主席树对应数组前i个元素的计数，查询时用r版本的树减去l-1版本的树，就能得到区间内的元素计数。时间复杂度O(n log k + m log k)，内存O(n log k)，完全适配大数据量在线查询。

• 能离线处理优先选莫队算法，内存和时间效率都最优；
• 元素数值范围小或可离散化、查询次数不多，选前缀数组+离散化；
• 必须在线处理查询，选主席树。

内容的提问来源于stack exchange，提问作者Noproblem 29