引言
在处理大规模区间查询问题时，我们经常会遇到一个困境：单个查询可以用简单的数据结构在 O(n) 或 O(log n) 内完成，但当查询数量达到 10^5 级别时，总时间复杂度将变得不可接受。莫队算法（Mo’s Algorithm）正是为解决这类离线区间查询问题而生的一种 elegant 的分块优化技巧。它由中国信息学竞赛选手莫涛在 2010 年提出，核心思想是通过对查询进行特殊的分块排序，使得相邻查询之间的区间移动代价最小化，从而将总复杂度从 O(nm) 优化到 O((n+m)√n)。本文将用 Java 实现莫队算法的完整框架，并以「区间最大频率」问题为例，展示其工程实践细节。
问题定义：区间最大频率
给定一个长度为 n 的整数序列 a[1..n]，以及 m 个查询。每个查询给出一个闭区间 [l, r]，要求返回该区间内出现次数最多的数值的出现次数。
例如序列 [1, 2, 1, 3, 2, 1]，查询区间 [1, 6] 时，数字 1 出现了 3 次，是频率最高的，因此答案为 3。
暴力解法的瓶颈
最直观的解法是：对于每个查询，遍历区间 [l, r] 统计每个数字的出现次数，然后取最大值。单次查询复杂度为 O(n)，m 次查询的总复杂度为 O(nm)。当 n 和 m 均为 10^5 时，运算量将达到 10^10，在 Java 中难以在合理时间内完成。
我们需要一种能够「批量处理」查询、并利用相邻查询之间关联性的方法。
分块思想：化整为零
莫队算法的第一个关键步骤是「分块」。我们将数组按照下标划分为大小为 B 的若干块（通常取 B = ⌈√n⌉）。第 i 个块包含下标范围 [(i-1)×B+1, i×B] 的元素。
分块的目的不是直接处理查询，而是为后续的「查询排序」提供依据。我们可以将每个查询 [l, r] 按照其左端点 l 所在的块编号进行分组，同一块内的查询再按右端点 r 排序。
莫队排序策略：让区间”少走冤枉路”
假设我们已经按上述规则对查询进行了排序。现在我们用两个指针 curL 和 curR 维护当前处理的区间，初始时 curL = 1, curR = 0（空区间）。
对于排序后的每一个查询 [L, R]，我们需要将 curL 移动到 L，将 curR 移动到 R。移动过程中，每向左/右扩展或收缩一格，就对「进入区间的元素」执行 add 操作，对「离开区间的元素」执行 remove 操作。
莫队排序的精妙之处在于：同一块内的查询，左端点 l 在同一区间内波动，而右端点 r 是单调递增的。这保证了指针的总移动距离被控制在 O(n√n) 级别。
更具体地说，对于左端点在同一块中的查询，curR 只会向右移动（或重置到块的起始位置后向右），因此右指针的总移动次数为 O(n × 块数) = O(n√n)。左指针在同一块内的移动距离不超过块大小 B = O(√n)，共有 m 个查询，因此左指针总移动次数为 O(m√n)。综合起来，总复杂度为 O((n+m)√n)。
双指针维护：O(1) 增删与最大频率追踪
莫队算法的第二个关键步骤是设计 O(1) 的 add 和 remove 操作。对于「区间最大频率」问题，我们维护以下数据结构：
cnt[v]：数值 v 在当前区间中的出现次数。freq[c]：当前区间中「出现次数恰好为 c」的不同数值有多少个。maxFreq：当前区间中的最大出现次数。
添加元素 x：
1. 获取 x 原来的出现次数 old = cnt[x]。
2. cnt[x]++。
3. freq[old]--，freq[old+1]++。
4. 如果 old + 1 > maxFreq，更新 maxFreq = old + 1。
删除元素 x：
1. 获取 x 原来的出现次数 old = cnt[x]。
2. cnt[x]--。
3. freq[old]--，freq[old-1]++。
4. 如果 freq[maxFreq] == 0，说明当前已经没有数值的出现次数达到 maxFreq，因此 maxFreq--。
通过 freq 数组的辅助，我们可以在 O(1) 时间内完成最大频率的更新与维护。
完整 Java 实现
以下是一个完整的、可直接运行的 Java 程序。程序包含快读优化、离散化、莫队排序、双指针维护以及结果输出。
import java.io.*;
import java.util.*;
/**
* 莫队算法实现：区间最大频率查询
*
* 核心思想：
* 1. 将所有查询按左端点分块排序，使得相邻查询的区间移动距离最小化。
* 2. 使用双指针维护当前区间，配合 O(1) 的增删操作统计最大频率。
*/
public class MoAlgorithm {
// 查询结构体，存储查询的原始编号、左右端点
static class Query {
int id; // 原始查询编号，用于按原顺序输出答案
int l, r; // 查询区间 [l, r]，采用 1-based 索引
Query(int id, int l, int r) {
this.id = id;
this.l = l;
this.r = r;
}
}
public static void main(String[] args) throws Exception {
// 使用 BufferedReader 加速输入读取
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// ========== 输入读取 ==========
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 序列长度
int m = Integer.parseInt(st.nextToken()); // 查询数量
int[] a = new int[n + 1]; // 原始数组，1-based
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
// ========== 离散化 ==========
// 将可能很大的原始数值映射到紧凑的 [1, K] 范围，降低数组开销
int[] sorted = Arrays.copyOfRange(a, 1, n + 1);
Arrays.sort(sorted);
int uniqueCount = 1;
for (int i = 1; i < sorted.length; i++) {
if (sorted[i] != sorted[i - 1]) {
sorted[uniqueCount++] = sorted[i];
}
}
int[] uniqueValues = Arrays.copyOf(sorted, uniqueCount);
for (int i = 1; i <= n; i++) {
a[i] = Arrays.binarySearch(uniqueValues, a[i]) + 1; // 映射为 1-based 编号
}
// ========== 读取查询 ==========
Query[] queries = new Query[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
queries[i] = new Query(i, l, r);
}
// ========== 莫队排序 ==========
int blockSize = (int) Math.sqrt(n); // 分块大小，通常取 sqrt(n)
if (blockSize == 0) blockSize = 1;
final int bs = blockSize;
Arrays.sort(queries, (q1, q2) -> {
int block1 = (q1.l - 1) / bs;
int block2 = (q2.l - 1) / bs;
if (block1 != block2) {
return block1 - block2; // 左端点所在块编号小的排前面
}
// 同一块内，右端点按升序排列（奇偶优化可进一步减少指针跳跃）
return q1.r - q2.r;
});
// ========== 初始化频率统计结构 ==========
// cnt[v]：离散化后数值 v 在当前区间中的出现次数
// freq[c]：当前区间中出现次数恰好为 c 的数值有多少个
int[] cnt = new int[uniqueCount + 2];
int[] freq = new int[n + 2]; // 最大频率不会超过区间长度 n
int maxFreq = 0; // 当前区间的最大出现次数
int curL = 1, curR = 0; // 当前维护的空区间 [1, 0]
int[] answers = new int[m]; // 存储每个查询的答案
// ========== 逐个处理排序后的查询 ==========
for (Query q : queries) {
int targetL = q.l;
int targetR = q.r;
// 扩展右边界：curR -> targetR
while (curR < targetR) {
curR++;
int val = a[curR];
int oldCount = cnt[val];
cnt[val] = oldCount + 1;
freq[oldCount]--;
freq[oldCount + 1]++;
if (oldCount + 1 > maxFreq) {
maxFreq = oldCount + 1;
}
}
// 收缩右边界：curR -> targetR
while (curR > targetR) {
int val = a[curR];
int oldCount = cnt[val];
cnt[val] = oldCount - 1;
freq[oldCount]--;
freq[oldCount - 1]++;
if (freq[maxFreq] == 0) {
maxFreq--;
}
curR--;
}
// 扩展左边界：curL -> targetL（向左移动，即减小 curL）
while (curL > targetL) {
curL--;
int val = a[curL];
int oldCount = cnt[val];
cnt[val] = oldCount + 1;
freq[oldCount]--;
freq[oldCount + 1]++;
if (oldCount + 1 > maxFreq) {
maxFreq = oldCount + 1;
}
}
// 收缩左边界：curL -> targetL（向右移动，即增大 curL）
while (curL < targetL) {
int val = a[curL];
int oldCount = cnt[val];
cnt[val] = oldCount - 1;
freq[oldCount]--;
freq[oldCount - 1]++;
if (freq[maxFreq] == 0) {
maxFreq--;
}
curL++;
}
// 记录当前查询的答案
answers[q.id] = maxFreq;
}
// ========== 按原始查询顺序输出结果 ==========
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
sb.append(answers[i]).append('\n');
}
System.out.print(sb.toString());
}
}
输入输出示例
输入：
6 3
1 2 1 3 2 1
1 6
2 4
3 5
输出：
3
1
1
解释：
– 查询 [1, 6]：数字 1 出现 3 次，答案为 3。
– 查询 [2, 4]：数字 2、1、3 各出现 1 次，答案为 1。
– 查询 [3, 5]：数字 1、3、2 各出现 1 次，答案为 1。
复杂度分析
时间复杂度：
– 排序阶段：对 m 个查询进行排序，复杂度为 O(m log m)。
– 指针移动阶段：左指针在每个块内的移动距离不超过块大小 B = O(√n)，共 m 个查询，总移动次数为 O(m√n)。右指针在每个块内单调移动，最多移动 O(n) 次，共有 O(√n) 个块，因此右指针总移动次数为 O(n√n)。
– 综合：总时间复杂度为 O(n√n + m√n + m log m)，在 n = m = 10^5 时约为 3×10^7 次操作，在 Java 中可以轻松通过。
空间复杂度：
– 离散化数组、cnt 数组、freq 数组以及查询数组，总空间复杂度为 O(n + m)。
进阶扩展
1. 希尔伯特序优化（Hilbert Order）
普通的分块排序在某些数据分布下可能导致右指针频繁”回跳”。希尔伯特序是一种空间填充曲线排序方式，它可以使得相邻查询在二维平面 (l, r) 上的曼哈顿距离更小，从而进一步减少指针移动次数。在实际竞赛中，使用希尔伯特序的莫队算法通常比普通分块排序快 30% 到 50%。
2. 带修改的莫队算法
当序列不仅存在区间查询，还存在「单点修改」操作时，可以将莫队算法扩展为三维版本。每个查询或修改操作被打上时间戳，排序规则变为 (l_block, r_block, time)。指针除了 curL 和 curR 之外，还需要维护一个「时间指针」，在向前或向后追溯时执行或撤销修改操作。时间复杂度为 O(n^(5/3))。
3. 树上莫队
莫队算法不仅适用于线性数组，也可以通过欧拉序（Euler Tour）将树结构转化为线性序列，从而在树上处理路径查询问题。将树节点的入序和出序展开后，一条树路径对应欧拉序中的一个或两个区间，配合莫队排序即可高效处理「树上路径颜色统计」等问题。
总结
莫队算法的魅力在于它「不修改数据结构本身，而是修改查询的处理顺序」。这种离线优化的思想在很多场景下都有借鉴意义。本文实现的完整 Java 程序展示了莫队算法的工程细节，包括离散化、分块排序、双指针增删以及最大频率的 O(1) 维护。读者可以在此基础上，将核心框架迁移到其他区间统计问题中，如区间不同元素个数、区间众数、区间频率前缀和等，体会这一算法的优雅与实用。
