莫队
在很久之前就听说了莫队。某河南省队爷来长沙培训的时候也讲了很多——然而事实上我还是不太会。七里八里终于搞了好久，算是明白了莫队的原理。
网上说莫队是传说中可以解决一切区间问题的东西。虽然这只是一个传说——例如10^5的区间求和这样的一种线段树树状数组随便搞的东西，莫队只能望尘莫及。但是有一些很强的问题，线段树树状数组完全不知下手的时候，也许莫队就可以水过。
扯了一下，具体来说说我个人对于莫队的理解。
莫队是一个离线算法。它的原理通过对询问的处理的顺序调整从而使得时间复杂度降低。
莫队是怎么操作的呢？在这里我以区间求和为例，阐述一下个人理解的普通莫队。
序列莫队
首先我们人为地把整个区间分为x块，每一块的长度为len。很显然，整个区间长度n=x*len。
接下来我们要保证在我们知道区间[l,r]的答案之后，我们可以在一个时间复杂度O(t)内求出[l,r+1]，[l,r-1]，[l+1,r]，[l-1,r]的答案。例如以区间求和，在知道[l,r]的区间和sum[l,r]之后，我们就可以O(1)求出这四个区间的区间和（此时t=1）。当然t是随着你操作的原理决定的。
那么接下来我们按照每一个询问左端点所在的块为第一关键字，询问的区间的右端点为第二关键字排一个序。
接下来我们按照这样的一个顺序对操作一个一个处理。
对于处理的方法，就是从询问[l[i],r[i]]一个一个推导到[l[i+1],r[i+1]]去，直到把询问处理完。
举个例子，比方说在区间[1..10]以内求区间和
下标：1 2 3 4 5 6 7 8 9 10
权值：2 2 1 0 3 4 7 2 3 4
对于这样的一个带权值的序列，我们要求
[1..9]
[2..7]
[5..6]
的区间和。
我们定义每一个块的长度为len=3，那么可以知道第一个询问[1..9]与第二个询问[2..7]为第一个块，第三个询问[5..6]为第二个块。这是可以O(1)求出来的。
那么接下来排序后就会变为
[2..7] [1..9] [5..6]
先定义一个nowl=1，nowr=1，nowsum=w[1..1]=2
接下来我们有[nowl,nowr]推广到[2..7]上去
[1,1]-[1,2]-[1,3]-[1,4]-[1,5]-[1,6]-[1,7]-[2,7]
这一个操作用了7次。接下来我们令nowl=2，nowr=7，nowsum=[2..7]，进行下一次推导。
以此类推。
为什么这样就可以降低复杂度呢？
首先我们考虑右端点移动：
在同一个块内右端点最坏会移动n次。
跨块的时候，右端点最坏移动n次。
上述两个操作均可能进行x次。
所以右端点移动的次数删去常数可以视为x*n次
接下来我们考虑左端点移动：
在同一个块内，如果这一个块内有qi个询问，每一次询问左端点最坏移动len次，所以一共移动qi*len次。一共有x个块，所以一共移动了q*len次（所有的qi加起来为q）。
每一次跨块的时候左端点最多移动2*len次（从上一个块的左端点移动到下一个块的右端点），一共可能会有x次移动，所以一共移动了x*2*len次。
所以左端点一共会移动(x+q)*len次。
所以总移动次数为
x*n+x*len+len*q
一次移动的时间复杂度是O(t)所以总的时间复杂度为 O(t)。
总时间复杂度为O(x*n*t+x*len*t+len*q*t)
我们把一个x=n/len换上去，就可以表示为
O(sqr(n)*t/len+n*t+len*q*t)
很多时候我们把t的操作时间视为1，q的范围视为n。
那么现在我们的时间复杂度就可以变为O(sqr(n)/len+n+len*n)，删去常数为O(sqr(n)/len+len*n)
由均值不等式可以得到
此时sqr(n)=sqr(len)*n，也就是说len=sqr(n)。此时时间复杂度最小。
删去常数就可以得到莫队一般的复杂度O(n*sqrt(n))。加上排序的时间复杂度，也就是O(n*sqrt(n)+nlogn)。删去常数还是可以算作O(n*sqrt(n))。
当然常数说大就真的有很大，因为只要出题人想卡莫队，常数可以达到10（好像有吧）。说小确定小，如果不卡莫队就还是挺不错的。当然，一般题目要么不会用莫队做（10^5的数据），要么只能用莫队做。
接下来我们还要讨论的就是这样的一个问题。
我们知道事实上莫队的复杂度为O(sqr(n)*t/len+n*t+len*q*t)。
我们把O当成一个与len相关的函数，记为O(len)。
这样写大家就明白我要表达的意思了。
根据具体的题目，我们可以知道n、q、t是一个常数，也就是说，这一个函数就是一个类似于f(x)=c/x+d*x+o。其中o与c是一个常数。
所以根据双勾函数的性质就可以得到：
当c/x=d*x的时候，使得函数f(x)最小。
所以可以得到：
删去常数可以得到
O(len)min=sqrt(q)*n*t
也就是说莫队复杂度的表达式为O(n*t*sqrt(q))，此时len=n/sqrt(q)。
回过来看，令t=1，q=n，莫队复杂度就变为了O(n*sqrt(n))。
终于证明完了。
最后来一段代码，以区间求和为例：
type
inf=record
num,l,r:longint;//num用来记录属于哪一个块（减小点常数，其实不必要），l与r记录询问的左端点与右端点
end;
var
a:array[1..1000] of longint;//记录整个区间
que:array[1..1000] of inf;//记录询问（questions）
n,q,i,len,nowl,nowr,sum:longint;
procedure swap(var a,b:longint);//交换
procedure sort(l,r:longint);
var
tl,tr,x,y,p:longint;
begin
tl:=l;
tr:=r;
p:=l+random(r-l+1);
x:=que[p].num;//以左端点所在的块为第一关键字，右端点为第二关键字来排序
y:=que[p].r;
repeat
while (que[tl].num<x)
or ((que[tl].num=x) and (que[tl].r<y)) do inc(tl);
while (que[tr].num>x)
or ((que[tr].num=x) and (que[tr].r>y)) do dec(tr);
if tl<=tr then
begin
swap(que[tl].num,que[tr].num);
swap(que[tl].l,que[tr].l);
swap(que[tl].r,que[tr].r);
inc(tl);
dec(tr);
end;
until tl>tr;
if l<tr then sort(l,tr);
if tl<r then sort(tl,r);
end;
function Moarr(now,l1,r1,l2,r2:longint):longint;//莫队转移
var
vi:longint;
begin//边界情况有点麻烦，要静下来思考
if r1<r2 then
for vi:=r1+1 to r2 do
inc(now,a[vi])
else
for vi:=r1 downto r2+1 do
dec(now,a[vi]);
if l1<l2 then
for vi:=l1 to l2-1 do
dec(now,a[vi])
else
for vi:=l1-1 downto l2 do
inc(now,a[vi]);
exit(now);
end;
begin
read(n);
for i:=1 to n do//读入
read(a[i]);
read(q);
len:=trunc(sqrt(n));
for i:=1 to q do
begin
read(que[i].l,que[i].r);
que[i].num:=que[i].l div len+1;//处理询问
end;
randomize;
sort(1,q);//询问排序
nowl:=1;
nowr:=1;
sum:=a[1];
for i:=1 to q do
begin
sum:=moarr(sum,nowl,nowr,que[i].l,que[i].r);//莫队推导
writeln(que[i].l,' ',que[i].r,' ',sum);
nowl:=que[i].l;
nowr:=que[i].r;
end;
end.
在线莫队
奇怪哈？
莫队本来就是一个离线算法，为何可以在线？
在线莫队事实上是一个暴力转移强行优化的结果。而且——也很快。
其思想是先预处理出每一个块的答案，之后求出每一个块构成的区间的答案。
接下来在做区间问题的时候，就可以先找到最接近的一段大的区间。之后再暴力转移即可。
再拿区间求和举个例子。
例如一个长度为10的序列：
1 2 6 8 7 3 2 4 9 8
令len=3（分为4块），变为了
1 2 6 8 7 3 2 4 9 8
现在处理处每一个块的答案。这个O(n)扫一遍即可得到答案。
Block[1..1]=1+2+6=9
Block[2..2]=8+7+3=18
Block[3..3]=2+4+9=15
Block[4..4]=8
接下来类似一个区间DP的方法，处理每一个由块组成的区间
Block[1..2]=Block[1..1]+Block[2..2]=27
Block[2..3]=Block[2..2]+Block[3..3]=33
其余的类似。
由于只有sqrt(n)个人块，所以这也是O(n)的。
接下来就可以回答询问了。假设要询问一段区间的和。
例如询问[1..7]，我们可以找到一个块[1..3]（也就是区间[1..9]）的和。我们先令sum=Block[1..3]，之后由区间[1..9]转移到[1..7]上去就可以 了。
显然这是一个O(qsqrt(n))的算法。
事实上取哪个块组成的区间都可以，只需要尽量接近询问区间就可以了。
不过有的时候要注意一下边界，例如最后一个块可能没有len个元素。区间长度设为len可能不能被n整除之类的。
代码如下（同样以区间求和为例）：
var
A:array[1..100000] of longint;//A数组
Block:array[1..400,1..400] of longint;//预处理的数组
n,i,j,k,l,r,q,num,len,sum:longint;
function Moarr(now,l1,r1,l2,r2:longint):longint;//莫队转移
var
vi:longint;
begin
if r1<r2 then
for vi:=r1+1 to r2 do
inc(now,A[vi])
else
for vi:=r1 downto r2+1 do
dec(now,A[vi]);
if l1<l2 then
for vi:=l1 to l2-1 do
dec(now,A[vi])
else
for vi:=l1-1 downto l2 do
inc(now,A[vi]);
exit(now);
end;
begin
read(n);//读入
for i:=1 to n do
read(A[i]);
len:=trunc(sqrt(n));
if n mod len=0 then num:=n div len//num为块的个数
else num:=n div len+1;
for i:=1 to num do//暴力求出由一个块组成的区间
begin
l:=len*(i-1)+1;
r:=l+len-1;
if r>n then r:=n;//注意最后一个区间元素可能没有len个
for j:=l to r do
inc(Block[i,i],A[j]);
end;
for j:=2 to num do//类似区间DP处理Block数组
for i:=1 to num do
begin
k:=i+j-1;
if k>num then break;
Block[i,k]:=Block[i,k-1]+Block[k,k];
end;
read(q);
for i:=1 to q do
begin
read(j,k);//读入询问
l:=(j-1) div len+1;
r:=k div len+1;//这个是可以自己定义的
if r>num then r:=num;
sum:=Block[l,r];//先将答案暂定为Block[l,r]，之后转移
l:=(l-1)*len+1;
r:=r*len;//只需要注意块对应的区间的l与r正确即可
if r>n then r:=n;
sum:=Moarr(sum,l,r,j,k);//转移
writeln(sum);//输出
end;
end.
一个细节
关于非计数问题？
如果不是计数问题，可能会出现在转移中右端点比左端点小的情况。这样可能会炸。
于是为了避免这样的情况——
在向左转移的时候，应该先令左端点转移
在向右转移的时候，应该先令右端点转移
即保证：
while(r<next[r])r++;在while(l<next[l])l++;前面
while(l>next[l])l--;在while(r>next[r])r--;前面。
即可。
拿“小z的袜子”一题做模板吧。
https://code.csdn.net/snippets/2145775
树上莫队
这里可以分为两个部分。
如果是子树查询的话，我们有一种叫做DFS序的东西，直接拿出来搞，当序列即可。
如果是树链查询的话，稍微有一点点复杂，我们看一种最简便的方法：
首先是排序的参数，我们做出DFS序，之后拿时间戳当参数，排序的关键字和序列上的是一样的。注意在这里，如果u的时间戳大于v的，需要交换u与v。
用S(v, u)代表 v到u的路径上的结点的集合。
用root来代表根结点，用lca(v, u)来代表v、u的最近公共祖先。
那么
S(v, u) = S(root, v) xor S(root, u) xor lca(v, u)
其中xor是集合的对称差。
简单来说就是节点出现两次消掉。
lca很讨厌，于是再定义
T(v, u) = S(root, v) xor S(root, u)
观察将curV移动到targetV前后T(curV, curU)变化：
T(curV, curU) = S(root, curV) xor S(root, curU)
T(targetV, curU) = S(root, targetV) xor S(root, curU)
取对称差：
T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU))
由于对称差的交换律、结合律：
T(curV, curU) xor T(targetV, curU)= S(root, curV) xorS(root, targetV)
两边同时xor T(curV, curU)：
T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV)
发现最后两项很爽……哇哈哈
T(targetV, curU)= T(curV, curU) xor T(curV, targetV)
（有公式恐惧症的不要走啊 T_T）
也就是说，更新的时候，xor T(curV, targetV)就行了。
即，对curV到targetV路径(除开lca(curV, targetV))上的结点，将它们的存在性取反即可。
——vfk博客
叽叽歪歪了这么多，至于操作，我们一般是先忽略掉lca，做转移，之后再把lca加回来。
拿一个最简单的例子，比方说我们维护桶，统计路径上的不同点权的数量。
我们需要一个点的存在性取反操作：
int nowans;
void reverse(const int &u) {
Bucket[col[u]]+=1-(vis[u]<<1);
if(vis[u]+Bucket[col[u]]==1)nowans+=1-(vis[u]<<1);
vis[u]^=1;
}
然后需要一个转移，其实是把两个点之间除了lca之外的点存在状态取反：
void Moarr(int x,int y) {
while(x!=y)
if(Depth[x]>Depth[y])reverse(x),x=Fm[x][0];
else reverse(y),y=Fm[y][0];
}
每一份操作，转移到(u,v)之后，把lca(u,v)的存在状态取反，然后计算完答案之后，再把lca(u,v)的状态取反：
for(i=2; i<=m; i++) {
Moarr(Q[i-1].u,Q[i].u);
Moarr(Q[i-1].v,Q[i].v);
l=lca(Q[i].u,Q[i].v);
reverse(l);
Ans[Q[i].num]=nowans;
reverse(l);
}
初始状态，我们直接转移到即可：
Moarr(Q[1].u,Q[1].v);
l=lca(Q[1].u,Q[1].v);
reverse(l);
Ans[Q[1].num]=nowans;
reverse(l);
这大致就是操作了。
带修改莫队
我觉得这玩意没什么用。复杂度极高。不够理想。
只能处理单点修改。
把时间按照一维拿过来排序。
排序第一关键字是l所在块，第二关键字是r所在块，第三关键字是时间。
注意在处理的时候，询问的时间是左边最近一个修改的编号。这样比较好转移。
大概是像这样：
for(i=1; i<=m; i++) {
for(opt=getchar(); opt!='Q'&&opt!='R'; opt=getchar());
if(opt=='Q') {
qtop++;
read(Q[qtop].l); read(Q[qtop].r);
Q[qtop].num=qtop; Q[qtop].tim=ctop;
} else {
ctop++;
read(O[ctop].p); read(O[ctop].to);
O[ctop].fr=A[O[ctop].p];
A[O[ctop].p]=O[ctop].to;
}
}
在转移的时候，可以先转移时间轴。
大致是这样：
while(nowtim<tim) {
nowtim++;
Change(O[nowtim].p,O[nowtim].fr,O[nowtim].to,nowl,nowr);
}
while(nowtim>tim) {
Change(O[nowtim].p,O[nowtim].to,O[nowtim].fr,nowl,nowr);
nowtim--;
}
注意，如果当前修改的位置不在当前询问的范围内，不需要计算贡献，只需要把原来的数组修改即可。
初始化的时候，时间的指针nowtim应该指在最末端。
然后跑莫队转移就可以了。
块的大小仍然可以设置为O(sqrt(n))。
可以参见本蒟的BZOJ_2120解题报告（虽然并没有写什么）。