1. 引言
莫队算法（Mo’s Algorithm）是一种用于高效处理离线区间查询问题的优雅算法。它由莫涛在 2009 年提出，通过巧妙地调整查询顺序，将时间复杂度从 O(n²) 优化至 O(n√n) 级别，成为解决大量静态区间查询问题的利器。
本文将系统性地介绍基础莫队算法的核心思想、实现步骤、复杂度分析，并通过经典例题（如区间内不同数字的个数）进行实战演练，帮助读者彻底掌握这一算法。
2. 算法核心思想
莫队算法的核心在于 “分块” 与 “离线处理”。
2.1 问题模型
我们通常面对的问题是：给定一个长度为 n 的序列 a[1…n]，以及 m 个离线查询，每个查询询问区间 [l, r] 的某个属性（如不同元素个数、区间和、众数等）。我们需要高效地回答所有查询。
2.2 暴力法的瓶颈
最直接的方法是对于每个查询，扫描整个区间 [l, r] 进行计算。总时间复杂度为 O(mn)，在 n 和 m 达到 10⁵ 级别时完全不可行。
2.3 莫队的优化思路
莫队算法观察到：相邻查询的区间往往有大量重叠部分。如果我们能从一个查询的答案 [l, r] 快速推导出下一个查询的答案 [l’, r’]，就能避免大量重复计算。
具体做法：
3. 算法实现步骤
3.1 数据结构准备
struct Query {
int l, r, id; // 查询区间 [l, r] 和查询编号
};
int n, m; // 序列长度，查询个数
int a[MAXN]; // 原序列
Query q[MAXM]; // 查询数组
int block_size; // 块大小
int ans[MAXM]; // 存储每个查询的答案
int cur_ans; // 当前区间 [cur_l, cur_r] 的答案
int cnt[MAXV]; // 计数数组，用于维护当前区间内每个值的出现次数（以统计不同数字为例）
3.2 排序函数
bool cmp(const Query &a, const Query &b) {
// 按左端点所在块排序，块号相同则按右端点排序
int block_a = a.l / block_size;
int block_b = b.l / block_size;
if (block_a != block_b) return block_a < block_b;
// 奇偶化排序优化：奇数块右端点升序，偶数块右端点降序，减少指针移动
return (block_a & 1) ? (a.r < b.r) : (a.r > b.r);
}
3.3 区间移动操作（以统计不同数字个数为例）
void add(int pos) {
// 将位置 pos 的元素加入当前区间
if (cnt[a[pos]] == 0) cur_ans++; // 之前没出现过，不同数字数+1
cnt[a[pos]]++;
}
void del(int pos) {
// 将位置 pos 的元素从当前区间移除
cnt[a[pos]]—;
if (cnt[a[pos]] == 0) cur_ans—; // 该数字出现次数归零，不同数字数-1
}
3.4 主算法流程
void mo() {
block_size = sqrt(n); // 设置块大小
sort(q, q + m, cmp); // 对查询排序
int cur_l = 1, cur_r = 0; // 当前维护的区间，初始为空区间 [1, 0]
cur_ans = 0;
for (int i = 0; i < m; i++) {
int l = q[i].l, r = q[i].r;
// 移动左指针 cur_l 到目标 l
while (cur_l > l) add(—cur_l);
while (cur_l < l) del(cur_l++);
// 移动右指针 cur_r 到目标 r
while (cur_r < r) add(++cur_r);
while (cur_r > r) del(cur_r—);
ans[q[i].id] = cur_ans; // 记录答案
}
}
4. 复杂度分析
4.1 时间复杂度
- 左指针移动：对于每个查询，左指针最多移动 O(√n) 次（因为左端点在同一个块内）。共有 m 个查询，所以总移动次数为 O(m√n)。
- 右指针移动：对于每个块，右指针单调移动，总移动次数为 O(n)。共有 O(√n) 个块，所以总移动次数为 O(n√n)。
- 总复杂度：O((n+m)√n)。当 n 和 m 同阶时，约为 O(n√n)。
4.2 空间复杂度
- 需要存储原序列、查询和答案数组，以及辅助计数数组，总空间复杂度为 O(n + m + max_value_range)。
5. 经典例题：区间不同数字个数
问题描述：给定一个长度为 n 的序列，m 次询问，每次询问区间 [l, r] 内有多少个不同的数字。
解决方案：这正是基础莫队的模板题。我们使用上面给出的代码框架，add 和 del 函数维护当前区间内每个数字的出现次数 cnt[] 以及不同数字的个数 cur_ans。
完整代码示例：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
const int MAXM = 200005;
const int MAXV = 1000005;
int n, m, block_size;
int a[MAXN], ans[MAXM], cnt[MAXV], cur_ans;
struct Query {
int l, r, id;
} q[MAXM];
bool cmp(const Query &a, const Query &b) {
int block_a = a.l / block_size;
int block_b = b.l / block_size;
if (block_a != block_b) return block_a < block_b;
return (block_a & 1) ? (a.r < b.r) : (a.r > b.r);
}
void add(int pos) {
if (cnt[a[pos]] == 0) cur_ans++;
cnt[a[pos]]++;
}
void del(int pos) {
cnt[a[pos]]—;
if (cnt[a[pos]] == 0) cur_ans—;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &q[i].l, &q[i].r);
q[i].id = i;
}
block_size = sqrt(n);
sort(q, q + m, cmp);
int cur_l = 1, cur_r = 0;
cur_ans = 0;
for (int i = 0; i < m; i++) {
int l = q[i].l, r = q[i].r;
while (cur_l > l) add(—cur_l);
while (cur_l < l) del(cur_l++);
while (cur_r < r) add(++cur_r);
while (cur_r > r) del(cur_r—);
ans[q[i].id] = cur_ans;
}
for (int i = 0; i < m; i++) printf("%d\\n", ans[i]);
return 0;
}
