莫队算法(Mo's Algorithm)

莫队算法是一类离线的区间查询处理技巧,核心思想是把所有询问重新排序,再用两个指针在序列上缓慢滑动,增量地维护当前区间对应的答案。它以竞赛选手莫涛的名字命名,在无法用数据结构直接维护的统计类查询上尤为有效。

概述

莫队算法要求所有查询能离线获取,即预先知道全部询问。它把序列分成大小约为根号n的块,再按左端点所在块为第一关键字、右端点为第二关键字对询问排序。这样处理相邻询问时,左右指针的总移动次数被控制在根号级别的均摊范围内。

核心原理

• 离线排序:按左端点分块、右端点排序,使指针移动的总代价最小化。
• 增量维护:每次把区间端点移动一格,通过加入或删除一个元素来更新答案。
• 复杂度:在分块大小取根号n时,总移动次数约为询问数乘序列长度的根号量级。
• 扩展形态:带修莫队引入时间维度,树上莫队把树的欧拉序列展开后套用同样思想。

应用场景

莫队算法适用于区间内不同元素个数、区间众数、区间逆序对等难以用线段树直接维护、但支持元素加入删除时增量更新的统计查询。它在算法竞赛中广泛应用,也可用于对静态数据的批量区间统计分析。

常见问题

问:莫队算法必须离线吗?答:标准莫队依赖对询问排序,因此必须离线;若强制在线,则通常需要换用可持久化数据结构等其他方案。

问:分块大小如何选取?答:通常取序列长度的平方根附近,可根据询问数与序列长度的比例微调,以在左右指针移动之间取得最佳平衡。