莫队算法，用来处理一类 离线 区间查询问题，具有编程复杂度低，易于扩展的优点。
可以方便地扩展到树上，也可以以一定的代价支持修改。
序列上 + 无修改
BZOJ 2038 小 Z 的袜子
这是最普通的莫队问题。
如果序列上询问区间 $[l, r]$ 上的答案可以 $O(1)$ 地扩展到 $[l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]$ 上，也就是说，我们能够 $O(1)$ 的添加和删除一个位置的贡献，那么莫队可以在 $O(n \sqrt n)$ 的时间内处理所有询问。
我们先来考虑基于区间转移的暴力：按顺序处理询问，每次暴力（一直移动区间端点，添加或删除一个位置的贡献，直到与当前区间相同）从上一个区间转移到下一个即可。
我们大概可以写出以下代码：
struct Query{
int l, r;
int id;
} querys[MAXM]; // 询问区间 [l, r]，id 代表在输入顺序中该询问的编号
int ans[MAXM]; // 每个询问的答案
bool in[MAXN]; // 每个元素的贡献是否在答案中
int l, r, currAns; // 维护当前区间 [l, r] 的答案是 currAns
void flip(int x){ // 将 x 的存在性取反
in[x] ^= 1;
if(in[x]){
// add the contribution of x into currAns;
} else{
// del the contribution of x from currAns;
}
}
void solve(){
l = 0, r = 0, currAns = 0, flip(0);
for(int i = 0; i < m; i++){
Query *q = &querys[i];
while(l > q->l) flip(--l);
while(r < q->r) flip(++r);
while(l < q->l) flip(l++);
while(r > q->r) flip(r--);
ans[q->id] = currAns;
}
}
每次转移的复杂度是 $O(n)$ 的，有 $O(m)$ 次转移，那么复杂度是 $O(nm)$ 的，我们以 $m, n$ 同阶（以下同），则复杂度是 $O(n^2)$ 的。
这个算法看起来并不比直接暴力优越，但我们考虑其意义，将区间 $[l, r]$ 看做二维平面上的点 $(l, r)$，可以看出，区间之间的转移代价是他们的「曼哈顿距离」。
（曼哈顿距离：平面上两个点 $(a, b)$ 和 $(c, d)$ 的曼哈顿距离为 $|a - c| + |b - d|$，即横纵坐标差的绝对值之和）
那么处理所有的询问相当于按照某种顺序走过所有点，所用总时间即为走过的曼哈顿距离之和。
一种可行的思路是，求出所有点的「最小曼哈顿距离生成树」，然后在生成树上走。
然而一点都不好写辣...
接下来我们说「莫队」的做法。
设置一个块的大小 $S$，根据左端点将询问分成若干块，即左端点为 $l$ 的询问被分到块 $\left \lfloor \frac l S \right \rfloor$ 中，然后在每一块中根据 $r$ 排序，然后块内暴力转移，块间也暴力转移。
另一种更简明的描述方法：按将询问按 $(\left \lfloor \frac l S \right \rfloor, r)$ 二元组排序，然后按这个顺序从前往后暴力转移。
可是等等，这可不就是把询问序列调了个顺序然后暴力嘛，怎么复杂度就变成 $O(n\sqrt n)$ 了呢？
然而确实是 $O(n\sqrt n)$，下面讨论时间复杂度。
我们先考虑块内的转移，对于每个询问，块内左端点移动是 $O(S)$ 的，对于每个块，总体来计，右端点的移动是 $O(n)$ 的，块数是 $O(\frac n S)$ 的，所以块内转移的总复杂度是 $O(nS + \frac {n^2} S)$ 的。
然后考虑块间的转移，每次转移是 $O(n)$ 的，块数是 $O(\frac n S)$ 的，所以块间转移的总复杂度是 $O(\frac {n^2} S)$ 的。
把两种转移加起来，算法的总复杂度是 $O(nS + \frac {n^2} S) = O(n (S + \frac n S))$，根据基本不等式，当 $S$ 取 $\sqrt n$ 时最优，这时的复杂度为 $O(n \sqrt n)$。
至于实现上，就是先计算 $S$，然后把询问按以上规则排序，之后暴力转移即可，代码与上面给出的完全一致。
可以在这篇文章中 [BZOJ 2038] 小 Z 的袜子 - 莫队 看到本题的完整代码。
序列上 + 带修改
BZOJ 2120 数颜色
如果带修改怎么办？
如果我们能够 $O(1)$ 地添加或删除一个修改的贡献，那么莫队算法可以在 $O(n^{\frac 5 3})$ 的时间内处理所有询问。
我们可以把考虑修改操作看成是添加一维，这一维是时间。
即把询问表示成 $(l, r, t)$ 的形式，其中 $t$ 表示在这之间有多少个询问。
可以把这看成三维空间上的点，然后暴力移动三个坐标以转移。
我们大概可以写出这样的代码：
struct Query{
int l, r, time;
int id;
} querys[MAXM]; // 询问区间 [l, r]，time 代表询问时间，或者说是在这之前的修改次数，id 代表在输入顺序中该询问的编号
int ans[MAXM]; // 每个询问的答案
bool in[MAXN]; // 每个元素的贡献是否在答案中
int l, r, currTime, currAns; // 维护当前询问 (l, r, currTime) 的答案是 currAns
void flip(int x){ // 将 x 的存在性取反
in[x] ^= 1;
if(in[x]){
// add the contribution of x into currAns;
} else{
// del the contribution of x from currAns;
}
}
void flipModification(int x){
// apply modification or invoke modification;
// if necessary, update currAns;
}
void solve(){
l = 0, r = 0, currAns = 0, currTime = 0, flip(0);
for(int i = 0; i < m; i++){
Query *q = &querys[i];
while(currTime < q->time) flipModification(currTime++);
while(currTime > q->time) flipModification(--currTime);
while(l > q->l) flip(--l);
while(r < q->r) flip(++r);
while(l < q->l) flip(l++);
while(r > q->r) flip(r--);
ans[q->id] = currAns;
}
}
保证时间复杂度的方法是，设定块的大小 $S_1, S_2$，将询问按 $(\left \lfloor \frac l S_1 \right \rfloor, \left \lfloor \frac r S_2 \right \rfloor, t)$ 三元组排序。
讨论下时间复杂度，以修改数、询问数均与 $n$ 同阶。
考虑这样的小块，其中的询问第一第二关键字相同，那么在块内，$t$ 的移动是 $O(n)$ 的，一共有 $O(\frac {n^2} {S_1S_2})$ 个块，所以转移 $t$ 的复杂度是 $O(\frac {n^3} {S_1S_2})$。
对于每个询问，$l$ 的移动是 $O(S_1)$ 的，$r$ 的移动是 $O(S_2)$ 的。
总的复杂度 $O(\frac {n^3} {S_1S_2} + nS_1 + nS_2) = O(n(\frac {n^2} {S_1S_2} + S_1 + S_2))$，根据（某种我不知道的数学技巧），当 $S_1 = S_2 = n^{\frac 2 3}$ 时最优，此时复杂度为 $O(n^{\frac 5 3})$
代码实现上，仍然是先计算 $S$，然后把询问按以上规则排序，然后像如上代码一样暴力转移即可。
可以在这篇文章中 [BZOJ 2120] 数颜色 - 带修改莫队 看到本题的完整代码。
树上 + 无修改
SPOJ COT2 Count on a tree II
接下来我们把莫队弄到树上去。~~（当然不是加个树链剖分）~~
原来的区间询问变成了树上路径询问。
如果我们能 $O(1)$ 的添加或删除一个点的贡献，那么莫队可以在 $O(n \sqrt n)$ 的时间内处理所有询问。
我们仍然先考虑暴力转移，这次我们转移的对象变成了路径，怎么办呢。
我们设 $R_i$ 表示从 $i$ 到根路径上的点集（包括 $i$），$(u, v)$ 表示从 $u$ 到 $v$ 路径上的点集，那么有：
$$ (u, v) = R_u \otimes R_v \otimes \{lca(u, v)\} $$
（其中 $\otimes$ 表示对称差运算，通俗地说就是出现两次的元素会被消掉）
我们要转移到 $u', v'$，也就是：
$$ (u', v') = R_{u'} \otimes R_{v'} \otimes \{lca(u', v')\} $$
根据对称差的性质，空集是单位元，任何集合都是其自身的逆元，以及交换律和结合律，有：
$$ \begin{align*} (u', v') & = (u, v) \otimes (\{lca(u, v)\} \otimes \{lca(u', v')\}) \otimes (R_u \otimes R_{u'}) \otimes (R_v \otimes R_{v'}) \\ & = (u, v) \otimes ({lca(u, v)} \otimes \{lca(u', v')\}) \otimes ((u, u') \otimes \{lca(u, u')\}) \otimes ((v, v') \otimes \{lca(v, v')\}) \end{align*} $$
在程序中实现对称差运算，就是对存在性取反，类似上面的 flip 函数。
那么实现这个转移的完整步骤就是这样的：
一、先对原来的 $lca(u, v)$ 取反，再对新的 $lca(u', v')$ 取反，其实这样就把原来的 $lca$ 替换成现在的了。
二、然后对路径 $(u, u')$ 上除 $lca(u, u')$ 以外的点取反，对路径 $(v, v')$ 上除 $lca(v, v')$ 以外的点取反，直接暴力遍历路径上的点即可。
我们大概可以写出如下代码（Node 类型是树上节点）：
struct Query{
Node *u, *v;
int time;
int id;
} querys[MAXM];
int currAns;
inline void flip(Node *v){ // 对 v 的存在性取反
v->in ^= 1;
if(v->in){
// add the contribution of v into currAns;
} else{
// del the contribution of v from currAns;
}
}
inline void flip(Node *u, Node *v){ // 对 (u, v) 路径上除 lca(u, v) 以外的点的存在性取反
Node *lca = queryLCA(u, v);
for(Node *p = u; p != lca; p = p->fa) flip(p);
for(Node *p = v; p != lca; p = p->fa) flip(p);
}
inline void solve(){
Node *u = nodes, *v = nodes, *lca = nodes;
currAns = 0, flip(nodes);
for(int i = 0; i < m; i++){
Query *q = &querys[i];
// 步骤一
flip(lca);
lca = queryLCA(q->u, q->v);
flip(lca);
// 步骤二
flip(u, q->u), u = q->u;
flip(v, q->v), v = q->v;
ans[q->id] = currAns;
}
}
下面讨论如何排序以保证时间复杂度。
首先你要会对树分块，所以请参见这道题目 [BZOJ 1086] 王室联邦 - 树分块。
这种分块的特点是块内任意两点间距离是 $O(S)$ 的。
排序方法是：将询问按照 $(blockId[u], dfn[v])$ 二元组排序。
和普通莫队的分析类似的，我们可以得到当 $S = \sqrt n$ 时，复杂度为 $O(n \sqrt n)$
可以在这篇文章中 Count on a tree II - 树上莫队 看到本题的完整代码。
树上 + 带修改
BZOJ 3052 糖果公园（在 UOJ 58 上也有此题）
~~（卡评测好题）~~
相信您看到这里，应该已经掌握了莫队的套路啦，对于这种带修改的情形，我们加一维时间就是咯。
排序依据是三元组 $(blockId[u], blockId[v], t)$，时间复杂度为 $O(n^{\frac 5 3})$
我还是把转移的大致代码给一下吧，作为参考：
struct Query{
Node *u, *v;
int id;
} querys[MAXM];
int currAns, currTime;
inline void flip(Node *v){ // 对 v 的存在性取反
v->in ^= 1;
if(v->in){
// add the contribution of v into currAns;
} else{
// del the contribution of v from currAns;
}
}
inline void flip(Node *u, Node *v){ // 对 (u, v) 路径上除 lca(u, v) 以外的点的存在性取反
Node *lca = queryLCA(u, v);
for(Node *p = u; p != lca; p = p->fa) flip(p);
for(Node *p = v; p != lca; p = p->fa) flip(p);
}
void flipModification(int x){
// apply modification or invoke modification;
// if necessary, update currAns;
}
inline void solve(){
Node *u = nodes, *v = nodes, *lca = nodes;
currAns = 0, currTime = 0, flip(nodes);
for(int i = 0; i < m; i++){
Query *q = &querys[i];
while(currTime < q->time) flipModification(currTime++);
while(currTime > q->time) flipModification(--currTime);
// 步骤一
flip(lca);
lca = queryLCA(q->u, q->v);
flip(lca);
// 步骤二
flip(u, q->u), u = q->u;
flip(v, q->v), v = q->v;
ans[q->id] = currAns;
}
}
可以在这篇文章中 [BZOJ 3052] 糖果公园 - 树上带修改莫队 看到本题的完整代码。
总结
总的来说，莫队算法还是比较好懂的，也十分好写，因为其本质是优化的暴力。
对莫队算法的扩展思路可能会给我们一些启示。
- 加一维支持修改
- 将序列问题扩展到树上 ~~或许也可以扩展到仙人掌上（雾~~
参考资料
莫队算法学习笔记, Sengxian
清橙A1206 小Z的袜子(莫队算法), 疯狂的橡树
WC 2013 糖果公园 park 题解, vfleaking