莫队算法

概念

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。

莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

核心思想

基本原理

莫队算法的核心是：如果已知区间 $[l,r]$ 的答案，能在 $O(1)$ 或 $O(\log n)$ 的时间内得到 $[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$ 的答案，那么可以通过合理安排询问的处理顺序，使得左右端点的总移动次数最小化。

分块排序

将所有询问离线后，按照以下规则排序：

1. 将序列分为大小为 $\sqrt{n}$ 的块。
2. 按左端点所在块编号为第一关键字排序。
3. 在同一块内，按右端点为第二关键字排序（奇偶块交替排序可进一步优化常数）。

排序后，依次处理每个询问，通过移动左右指针 $l$、$r$ 来增删元素，维护当前区间的答案。

复杂度分析

• 右端点：在同一块内单调递增，跨块时最多回退 $n$ 步，共 $\sqrt{n}$ 个块，总移动 $O(n\sqrt{n})$。
• 左端点：同一块内移动不超过 $\sqrt{n}$，共 $q$ 个询问，总移动 $O(q\sqrt{n})$。
• 综合：$O((n+q)\sqrt{n})$。

时间复杂度

变体	时间复杂度	说明
普通莫队	$O((n+q)\sqrt{n})$	离线区间询问
带修莫队	$O(n^{5/3})$	支持单点修改，块大小取 $n^{2/3}$
树上莫队	$O((n+q)\sqrt{n})$	通过欧拉序转化为序列问题
回滚莫队	$O((n+q)\sqrt{n})$	只支持插入不支持删除时使用

适用场景

• 离线区间查询，且增删一个元素能快速更新答案（如区间不同数个数、区间众数相关统计）
• 无法用线段树等在线数据结构高效维护的区间统计问题
• 树上路径查询（通过欧拉序转化）
• 带少量修改操作的区间查询（带修莫队）

参考

• OI Wiki - 莫队算法简介