chat
详细介绍一下 莫队算法（Mo’s Algorithm）
莫队算法（Mo’s Algorithm）详解
莫队算法是一种高效的离线算法，专门用于解决区间查询问题。
通过对查询进行排序，结合滑动窗口的思想，可以显著降低算法复杂度。
基本思想
莫队算法通过以下步骤高效处理查询：
- 重排查询顺序：按一定规则排序查询，减少移动范围时的重复计算。
- 滑动窗口：维护一个动态区间，通过移动左右指针动态更新答案。
- 分块优化：按数组大小分块，使指针移动范围局限于相邻块内，进一步减少移动次数。
时间复杂度
- 查询排序的复杂度：O(Q log Q)，其中 Q 是查询的个数。
- 滑动窗口的移动复杂度：O((N + Q) sqrt(N))，其中 N 是数组长度，滑动窗口的移动次数与分块大小相关。
总时间复杂度：O((N + Q) sqrt(N))。
适用场景
莫队算法适合以下问题：
- 区间统计问题：如区间内不同数字的个数、区间内的和、乘积等。
- 离线查询：所有查询提前给出，允许我们对查询进行预处理和排序。
要求：
- 查询可以离线计算。
- 查询的顺序不影响答案。
实现步骤
1. 查询排序规则
将查询按以下规则排序：
- 按左端点 (L) 所在的块编号（块大小为 sqrt(N)）升序排列；
- 同一块内的查询，按右端点 (R) 排序：
- 奇数块按 (R) 升序排列；
- 偶数块按 (R) 降序排列（减少指针大幅度跳跃）。
2. 滑动窗口处理
用两个指针 (currL) 和 (currR) 表示当前窗口的左右端点：
- 如果 (currL < L)，右移 (currL)，从窗口中移除左端的元素；
- 如果 (currL > L)，左移 (currL)，向窗口添加左端的元素；
- 如果 (currR < R)，右移 (currR)，向窗口添加右端的元素；
- 如果 (currR > R)，左移 (currR)，从窗口中移除右端的元素。
3. 动态更新答案
每次移动指针时，根据新增或移除的元素动态更新答案。
示例：区间内不同数字的个数
问题描述
给定一个数组 arr 和若干查询，每个查询形式为 (L, R)，问区间 [L, R] 内有多少个不同的数字。
实现代码
import java.util.*;
public class MoAlgorithm {
static class Query implements Comparable<Query> {
int l, r, index;
Query(int l, int r, int index) {
this.l = l;
this.r = r;
this.index = index;
}
@Override
public int compareTo(Query other) {
int blockSize = (int) Math.sqrt(MoAlgorithm.n);
int block1 = this.l / blockSize;
int block2 = other.l / blockSize;
if (block1 != block2) {
return block1 - block2; // 按块排序
}
return (block1 % 2 == 0) ? (this.r - other.r) : (other.r - this.r); // 按右端点排序
}
}
static int n; // 数组长度
static int[] arr; // 数组
static int[] freq; // 数字出现频率
static int distinctCount; // 当前窗口的不同数字个数
// 增加一个数字到窗口
static void add(int x) {
freq[x]++;
if (freq[x] == 1) {
distinctCount++;
}
}
// 从窗口移除一个数字
static void remove(int x) {
if (freq[x] == 1) {
distinctCount--;
}
freq[x]--;
}
public static void main(String[] args) {
// 示例输入
arr = new int[]{1, 1, 2, 1, 3};
n = arr.length;
Query[] queries = {
new Query(1, 3, 0),
new Query(2, 4, 1),
new Query(0, 4, 2)
};
// 初始化频率数组和查询答案
freq = new int[100001]; // 假设数组元素范围较小
int[] answers = new int[queries.length];
// 查询排序
Arrays.sort(queries);
// 滑动窗口初始化
int currL = 0, currR = 0;
distinctCount = 0;
// 遍历查询
for (Query query : queries) {
int l = query.l, r = query.r;
while (currL < l) {
remove(arr[currL]);
currL++;
}
while (currL > l) {
currL--;
add(arr[currL]);
}
while (currR <= r) {
add(arr[currR]);
currR++;
}
while (currR > r + 1) {
currR--;
remove(arr[currR]);
}
// 保存结果
answers[query.index] = distinctCount;
}
// 输出结果
System.out.println(Arrays.toString(answers));
}
}
输入与输出
输入
数组 arr = [1, 1, 2, 1, 3]
查询：[(1, 3), (2, 4), (0, 4)]
输出
[2, 3, 3]
- 第一个查询
(1, 3)区间内的不同数字有{1, 2}，个数为 2； - 第二个查询
(2, 4)区间内的不同数字有{1, 2, 3}，个数为 3； - 第三个查询
(0, 4)区间内的不同数字有{1, 2, 3}，个数为 3。
实现分析
- 查询排序：将查询按分块规则排序，复杂度 O(Q log Q)。
- 滑动窗口：每次通过指针移动更新窗口内容，单次更新复杂度为 O(sqrt(N))。
- 灵活性强：可适配区间和统计问题。
优点与局限性
优点
- 高效：时间复杂度 O((N + Q) sqrt(N))，非常适合大规模数据。
- 通用性强：适合多种区间统计问题。
局限性
- 实现复杂：需要严格管理窗口的增删操作。
- 仅适用于离线查询：无法用于实时查询。
通过理解和应用莫队算法，可以解决许多高效区间查询问题，是竞赛与实际开发中的强大工具。
莫队算法（Mo’s Algorithm）的应用场景
莫队算法（Mo’s Algorithm）是一种处理区间查询和区间更新问题的有效算法，特别适用于处理大量区间查询的问题。
以下是莫队算法的一些主要应用场景：
- 区间统计问题：
- 统计区间内的不同数字数量，例如在给定数组中查询某个区间内有多少个不同的数字。
- 逆序对问题：
- 计算数组中的逆序对数量，逆序对问题可以转化为区间问题，通过莫队算法进行优化。
- 区间修改问题：
- 在数组中进行区间更新操作，如区间加法，可以通过莫队算法高效处理。
- 树上问题：
- 树形结构上的路径问题，通过将树的节点顺序转换为一维数组，利用莫队算法求解路径问题。
- 离线和在线问题：
- 莫队算法不仅可以用于离线处理问题，还可以通过在线化改造来处理在线问题。
- 统计多个区间：
- 对于多个区间的统计问题，莫队算法通过移动左右指针与每个询问的区间匹配，高效地得到多个区间询问的答案。
- 带修改的莫队：
- 对于带修改的莫队算法，可以处理更复杂的区间问题，如区间内的数值更新。
- 几何问题：
- 在计算几何问题中，莫队算法可以用来处理区间内点的查询和更新，如点的包含关系、最近邻搜索等。
- 动态规划问题：
- 在解决一些动态规划问题时，莫队算法可以用来高效地处理状态的更新和查询。
莫队算法因其高效的区间处理能力，在需要处理大量区间查询和更新的场景下特别有用，尤其是在算法竞赛和数据密集型应用中。
通过将问题转化为一维数组的区间问题，莫队算法可以显著提高处理效率。
为什么莫斯算法可以提升这种查询性能呢？原理是什么？
性能提升的关键点
-
查询排序减少窗口调整代价：
-
排序后相邻查询的范围变化较小，端点
L, R只需要微调。 -
每次微调仅需处理新增或移除的元素。
-
-
增量计算避免重复工作：
-
在调整窗口时，利用已有的中间结果，仅针对增量部分更新。
-
例如，对于求区间最小值问题，只需要更新新增或移除的数值，而不需要重新扫描整个区间。
-
-
适合大规模查询：
- 如果有很多查询，排序开销可以被滑动窗口的高效调整所抵消，尤其是对于
q >> n的情况。
- 如果有很多查询，排序开销可以被滑动窗口的高效调整所抵消，尤其是对于
适用问题类型
莫队算法适用于 静态区间查询，即数据不变，但需要对多个区间进行查询的问题。
例如：
-
区间统计： 计算某个区间的频率分布。
-
区间和： 求某个区间的元素和。
-
区间最值： 求某个区间的最大值或最小值。
-
区间答案依赖相邻性： 例如最小绝对差、不同元素个数等。
为什么区间排序有用？
查询排序的目的是减少 L 和 R 的移动距离：
-
排序后，相邻查询的起点
L和终点R改变幅度较小。 -
通过滑动
L和R来逐步调整区间，避免重新计算整个区间。
例如：
-
原始查询
[1, 10],[5, 15],[3, 8]。 -
排序后可能变为
[1, 10],[3, 8],[5, 15]，使相邻区间的调整范围最小化。
时间复杂度分析
- 查询排序的时间复杂度为
O(q * log(q))（对q个查询排序）。 - 每次滑动窗口的操作复杂度为
O(sqrt(n))，因为最多移动sqrt(n)次。 - 因此，整体时间复杂度为
O(q * sqrt(n) + q * log(q))。
当 q >> n 时，排序代价 O(q * log(q)) 可以忽略，复杂度约为 O(q * sqrt(n))。
最终，莫队算法通过排序和滑动窗口的结合，将暴力方法的复杂度从 O(n * q) 优化为 O(q * sqrt(n))，尤其适用于 n 和 q 都较大的情况下。
如何记忆？
你可以按照以下几个核心概念来理解和记住这个算法：
1. 问题类型
莫斯算法适用于解决 区间查询 问题，特别是对于 静态数组 和需要处理多个 区间查询 的情况。
比如：
- 区间最小值或最大值查询
- 区间和查询
- 区间内的某些统计信息（比如频次、不同元素个数等）
2. 核心思想：
查询排序 + 滑动窗口。
- 将查询按照区间的左右端点
(L, R)排序，排序时让相邻查询尽量靠近。 - 使用 滑动窗口（移动指针）来逐步调整区间，避免每次查询都从头扫描整个数组。
- 增量计算：每次滑动窗口时，只处理进入窗口的新元素和离开窗口的元素。
3. 步骤记忆：
- 排序查询：
- 先对所有查询按照 左端点
L的位置排序。 - 对 右端点
R排序，通常按R / sqrt(n)分块排序（因为sqrt(n)可以帮助最小化每次窗口的变化）。
- 先对所有查询按照 左端点
- 滑动窗口：
- 使用两个指针（
L和R）表示当前区间。起始时，两个指针都指向数组的开始。 - 根据排序后的查询，逐一处理每个区间。
- 在处理查询时，按排序后的顺序， 扩展 或 收缩 区间：
- 向右移动
R增加右端元素 - 向左移动
L移除左端元素
- 向右移动
- 每次调整时，利用已有的信息 增量更新。
- 使用两个指针（
- 更新答案：
- 每次滑动窗口时，检查区间内的信息（比如最小值、频率等）。
- 完成每个查询后，记录结果。
4. 为什么使用排序：
排序查询的目的是 最小化窗口的调整，使得相邻的查询尽量不需要太多移动。
排序后，左端点和右端点的变化较小，所以窗口的变化幅度小，能大大减少重复计算。
5. 时间复杂度：
- 查询排序：排序
q个查询，时间复杂度是O(q log q)。 - 滑动窗口调整：每次调整窗口时，最多需要移动
L或R指针sqrt(n)次。所以每次处理一个查询的复杂度是O(sqrt(n))。 - 总时间复杂度：
O(q * sqrt(n) + q log q)。
6. 记忆提示：
- 分块：将所有查询按照
sqrt(n)分成若干块，排序时按块分配。 - 滑动窗口：窗口大小动态变化，指针
L和R通过增量更新。 - 排序：排序的目的是减少区间左右端点的变化。
leetcode 中莫队算法（Mo’s Algorithm）相关的经典题目，包含链接
以下是一些在 LeetCode 上与莫队算法（Mo’s Algorithm）相关的经典题目以及对应的题目链接：
在 LeetCode 上，莫队算法（Mo’s Algorithm）常用于解决一些范围查询类型的问题，尤其是当你需要进行多次查询时，能够通过减少重复计算来提高效率。以下是一些经典的适合使用莫队算法的题目：
- Q350. Intersection of Two Arrays II
- 该题目要求你找出两个数组的交集，其中数组的元素可能有重复。虽然不完全适用于莫队算法，但如果你对范围查询感兴趣，这可以作为一个起点来理解莫队的思想。
- Q1020. Number of Enclaves
- 这题需要在一个二维网格上找到不与边界接触的岛屿区域，适合通过不同的查询来计算连通区域等。
- Q303. Range Sum Query - Immutable
- 这个题目要求你计算数组某一段区间的和。通过莫队算法可以有效处理多个区间求和的操作。
- Q1052. Grumpy Bookstore Owner
- 题目要求你根据店主心情和客户数量最大化在某一段时间内的客户数，莫队算法可以用于区间优化问题。
- Q1273. Delete Tree Nodes
- 虽然这个题目本身更适合动态规划或树的操作，但如果涉及到对树的某些部分进行快速查询，莫队算法也是一个有用的思路。
- Q1146. Snapshot Array
- 该题涉及多个时间戳的查询操作，适合使用莫队算法来优化对快照数据的处理。
尽管莫队算法并不直接适用于所有范围查询问题，但它非常适合解决“区间求和”类题目，尤其是当有多个查询时。如果你正在学习或应用莫队算法，可以从这些题目入手进行实践。
