引言
莫队算法（Mo’s Algorithm）是由前国家队队长莫涛在2010年左右提出的一种离线区间查询优化算法。它通过对查询区间进行巧妙的分块排序，将朴素O(n×q)的区间查询优化到O((n+q)×√n)，在处理大量区间统计问题时展现出惊人的效率。本文将用Java实现莫队算法，以”区间不同元素个数”这一经典问题为例，深入讲解其分块排序策略与指针移动优化。
算法核心思想
问题背景
给定一个长度为n的数组和q个查询，每个查询要求区间[l, r]内不同元素的个数。如果对每个查询都遍历区间统计，时间复杂度为O(n×q)，在n,q≤10^5时无法接受。
莫队算法的核心思想
莫队算法的精髓在于利用相邻查询之间的重叠性。如果我们已经知道区间[L, R]的答案，可以通过移动L和R指针来得到新区间的答案，每次移动只影响一个元素的增减。
关键在于查询的排序方式：将数组分为√n个块，按左端点所在块排序，同一块内按右端点排序（奇偶块优化时右端点交替升降）。这样相邻查询的指针移动总量被控制在O((n+q)×√n)。
奇偶块优化
标准莫队中，同一块内的查询按右端点升序排列。进一步优化采用”奇升偶降”策略：奇数块的查询右端点升序，偶数块的查询右端点降序。这样可以减少右指针的来回跳跃。
完整Java实现
import java.util.*;
/**
* 莫队算法（Mo's Algorithm）实现
* 用于高效处理离线区间查询问题
* 本例以求解"区间不同元素个数"为例
*/
public class MoAlgorithm {
/**
* 查询结构体
* 存储查询的左右端点、原始索引
*/
static class Query {
int left, right, index, blockId;
Query(int left, int right, int index, int blockSize) {
this.left = left;
this.right = right;
this.index = index;
this.blockId = left / blockSize;
}
}
private final int[] arr; // 原始数组
private final int n; // 数组长度
private final int blockSize; // 块大小
// 频率统计与当前答案
private final Map<Integer, Integer> freq; // 各元素在当前区间出现的次数
private int distinctCount; // 当前区间内不同元素的个数
public MoAlgorithm(int[] arr) {
this.arr = arr;
this.n = arr.length;
this.blockSize = (int) Math.sqrt(n) + 1; // 块大小取√n
this.freq = new HashMap<>();
this.distinctCount = 0;
}
/**
* 添加一个元素到当前区间
* @param position 元素在数组中的位置
*/
private void add(int position) {
int val = arr[position];
int count = freq.getOrDefault(val, 0);
if (count == 0) {
distinctCount++; // 新元素首次出现
}
freq.put(val, count + 1);
}
/**
* 从当前区间移除一个元素
* @param position 元素在数组中的位置
*/
private void remove(int position) {
int val = arr[position];
int count = freq.get(val);
if (count == 1) {
distinctCount--; // 该元素唯一出现，移除后减少不同元素数
freq.remove(val);
} else {
freq.put(val, count - 1);
}
}
/**
* 处理所有查询
* @param queries 查询数组，每个元素为[left, right]
* @return 每个查询的答案数组
*/
public int[] processQueries(int[][] queries) {
int q = queries.length;
Query[] sortedQueries = new Query[q];
// 构建查询对象
for (int i = 0; i < q; i++) {
sortedQueries[i] = new Query(queries[i][0], queries[i][1], i, blockSize);
}
// 莫队排序：按块编号排序，同一块内奇偶优化
Arrays.sort(sortedQueries, (a, b) -> {
if (a.blockId != b.blockId) {
return Integer.compare(a.blockId, b.blockId);
}
// 奇偶优化：奇数块右端点升序，偶数块右端点降序
return (a.blockId % 2 == 0)
? Integer.compare(a.right, b.right)
: Integer.compare(b.right, a.right);
});
int[] answers = new int[q];
// 初始区间为[0, -1]，表示空区间
int currentLeft = 0;
int currentRight = -1;
// 按排序后的顺序处理每个查询
for (Query query : sortedQueries) {
int L = query.left;
int R = query.right;
// 扩展右边界
while (currentRight < R) {
currentRight++;
add(currentRight);
}
// 收缩右边界
while (currentRight > R) {
remove(currentRight);
currentRight--;
}
// 收缩左边界
while (currentLeft < L) {
remove(currentLeft);
currentLeft++;
}
// 扩展左边界
while (currentLeft > L) {
currentLeft--;
add(currentLeft);
}
answers[query.index] = distinctCount;
}
return answers;
}
/**
* 重置状态，用于多次查询
*/
public void reset() {
freq.clear();
distinctCount = 0;
}
/**
* 主程序：演示莫队算法
*/
public static void main(String[] args) {
// 示例数组
int[] arr = {1, 1, 2, 1, 3, 4, 5, 2, 3, 1, 4, 5, 2};
System.out.println("数组: " + Arrays.toString(arr));
MoAlgorithm mo = new MoAlgorithm(arr);
// 定义查询区间 [left, right]，闭区间
int[][] queries = {
{0, 4}, // [1,1,2,1,3] -> 3个不同元素
{1, 6}, // [1,2,1,3,4,5] -> 5个不同元素
{2, 8}, // [2,1,3,4,5,2,3] -> 5个不同元素
{0, 12}, // 整个数组 -> 5个不同元素
{5, 9}, // [4,5,2,3,1] -> 5个不同元素
{3, 7}, // [1,3,4,5,2] -> 5个不同元素
};
System.out.println("\n查询区间及答案:");
int[] answers = mo.processQueries(queries);
for (int i = 0; i < queries.length; i++) {
int[] sub = Arrays.copyOfRange(arr, queries[i][0], queries[i][1] + 1);
System.out.printf("[%d, %d] %s -> %d 个不同元素%n",
queries[i][0], queries[i][1], Arrays.toString(sub), answers[i]);
}
// 大规模性能测试
System.out.println("\n大规模性能测试 (n=100000, q=100000):");
int n = 100000;
int q = 100000;
int[] largeArr = new int[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) {
largeArr[i] = rand.nextInt(1000) + 1;
}
int[][] largeQueries = new int[q][2];
for (int i = 0; i < q; i++) {
int l = rand.nextInt(n);
int r = rand.nextInt(n);
if (l > r) { int t = l; l = r; r = t; }
largeQueries[i][0] = l;
largeQueries[i][1] = r;
}
MoAlgorithm largeMo = new MoAlgorithm(largeArr);
long start = System.currentTimeMillis();
largeMo.processQueries(largeQueries);
long elapsed = System.currentTimeMillis() - start;
System.out.println("莫队算法耗时: " + elapsed + "ms");
// 对比朴素算法
start = System.currentTimeMillis();
for (int i = 0; i < q; i++) {
Set<Integer> set = new HashSet<>();
for (int j = largeQueries[i][0]; j <= largeQueries[i][1]; j++) {
set.add(largeArr[j]);
}
}
long naiveTime = System.currentTimeMillis() - start;
System.out.println("朴素算法耗时: " + naiveTime + "ms");
System.out.println("加速比: " + (double) naiveTime / elapsed + "x");
}
}
关键算法解析
1. 分块排序策略
莫队算法的排序规则为：先按左端点所在块排序，同一块内按右端点排序。这样排序后，左指针在同一块内只需在块大小范围内移动，右指针单调移动（或近似单调）。总移动次数为O((n+q)×√n)。
2. 指针移动的均摊分析
设块大小为B=√n：
– 左指针移动：相邻查询若在同一块，左指针移动O(B)；跨块时可能移动O(n)，但最多跨n/B次块。总计O(q×B + n×n/B) = O((n+q)×√n)。
– 右指针移动：同一块内右指针单调移动，总移动O(n×n/B) = O(n×√n)。
3. 奇偶块优化
标准排序中右指针在同一块内单调移动，但跨块时需要从末尾跳回开头。奇偶优化让偶数块右端点降序排列，使右指针跨块时就近衔接，减少跳跃距离。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 排序 | O(q log q) | 对q个查询排序 |
| 单次add/remove | O(1) | 哈希表统计频率 |
| 总指针移动 | O((n+q)×√n) | 左指针O(q×√n)，右指针O(n×√n) |
| 总时间 | O((n+q)×√n) | 莫队算法的核心复杂度 |
| 空间 | O(n) | 频率哈希表 |
总结
莫队算法是离线区间查询问题的利器，其核心贡献在于发现了”查询顺序”对总计算量的影响。通过分块排序，将看似独立的查询串联起来，利用区间重叠减少重复计算。
适用场景：
1. 离线查询：所有查询已知，可以重新排序
2. 可逆操作：能够通过add和remove维护区间状态
3. 无修改：或修改操作也可以用”带修改莫队”扩展
本文实现的莫队算法以”不同元素个数”为例，该框架可以扩展到区间众数、区间频率统计等多种问题。
