当前位置：首页 > news >正文

莫队算法C/C++实现

news 2025/11/24 1:14:15

简介

算法原理

算法步骤

C++ 实现

应用场景

莫队算法（Mo's Algorithm）是一种用于解决区间查询和更新问题的算法，由俄罗斯选手莫洛佐夫（Mo Morozov）提出。它在算法竞赛和某些计算密集型任务中非常有用，尤其是在需要处理大量区间查询和更新操作时。莫队算法以其高效性和简洁性而闻名，特别适合处理离线问题，即所有查询都已知且不需要实时处理。

简介

在算法竞赛和某些计算密集型任务中，我们经常需要处理大量的区间查询和更新操作。传统的线段树或树状数组虽然能够处理这类问题，但在面对大量数据时，效率往往不尽如人意。莫队算法（Mo's Algorithm），由俄罗斯选手莫洛佐夫（Mo Morozov）提出，是一种高效的离线算法，特别适用于处理区间查询和更新问题。

算法原理

莫队算法的核心思想是将所有的查询按照结束时间排序，然后使用一个双向指针扫描区间，这样可以保证在任何时刻，被处理的区间都是当前未结束的最小区间。算法的时间复杂度为 (O((n + q) \log n)，其中 n 是区间的数量，q 是查询的数量。

算法步骤

1. 排序：将所有的查询按照结束时间进行排序。
2. 初始化：使用一个数组记录每个区间的活跃状态。
3. 扫描：使用两个指针，一个从左向右扫描，一个从右向左扫描，同时更新区间的活跃状态。
4. 处理查询：在扫描过程中，对于每个查询，根据当前的区间活跃状态计算结果。

C++ 实现

下面是一个简单的莫队算法的C++实现，用于计算区间和的查询。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>using namespace std;struct Query {int l, r, id;
};int main() {int n, q;cin >> n >> q;vector<int> a(n + 1);vector<Query> queries(q);for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 0; i < q; ++i) {cin >> queries[i].l >> queries[i].r;queries[i].id = i;}// 按照结束位置排序sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {return a.r < b.r;});vector<int> active(n + 1, 0);vector<long long> sums(q, 0);int j = 0;for (int i = 0, k = 0; i < q; ++i) {while (k < q && queries[k].r == i) {++active[queries[k].l];k++;}while (j < q && queries[j].l <= i) {--active[queries[j].r + 1];j++;}long long sum = 0;for (int p = 1; p <= n; ++p) {if (active[p]) {sum += a[p];}}sums[queries[i].id] = sum;}for (int i = 0; i < q; ++i) {cout << sums[i] << endl;}return 0;
}