需要注意的是，修改分为两部分：

1. 若修改的位置在当前区间内，需要更新答案（(mathrm{del})原颜色，(mathrm{add})修改后的颜色）。
2. 无论修改的位置是否在当前区间内，都要进行修改（以供(mathrm{add})和(mathrm{del})函数在以后更新答案）。

分块大小的选择以及复杂度证明

（用(B)表示分块大小，(c)表示修改个数，(q)表示询问个数，(l)块表示以(l div B)分的块，每个(l)块包含(n div B)个(r)块）

1. 对于时间指针(mathrm{now})：对于每个r块，最坏情况下会移动(c)，共有(left(frac{n}{B}right)^2)个(r)块，所以总移动次数为(frac{cn^2}{B^2})。
2. 对于左端点指针(l) ：(l)块内移动每次最多(B)，换(l)块每次最多(2B)，所以总移动次数为(O(qB))。
3. 对于右端点指针(r)：(r)块内移动每次最多(B)，换(r)块每次最多(2B)，所有(l)块内移动次数之和为(O(qB))；换(l)块时最多移动(n)，总的换(l)块时移动次数为(Oleft(frac{n^2}{B}right))；所以总的移动次数为(Oleft(qB+frac{n^2}{B}right))。

所以：总移动次数为(Oleft(frac{cn^2}{B^2}+qB+frac{n^2}{B}right))。

由于一般的题目都不会告诉你修改和询问分别的个数，所以统一用(m)表示，即(Oleft(frac{mn^2}{B^2}+mB+frac{n^2}{B}right))。

(B)可以取[frac{n^{2}}{3^{frac{1}{3}}(9m^{3}n^{2}+sqrt{3}sqrt{27m^{6}n^{4}-m^{3}n^{6}})^{frac{1}{3}}}+frac{(9m^{3}n^{2}+sqrt{3}sqrt{27m^{6}n^{4}-m^{3}n^{6}})^{frac{1}{3}}}{3^{frac{2}{3}}m}]

所以还是不要纠结带修莫队的最佳分块大小好了(cdotscdots)视作(n=m)的话，就可以得到总移动次数为(Oleft(frac{n^3}{B^2}+nB+frac{n^2}{B}right))，那么(B=n^{frac{2}{3}})时取最小值(Oleft(n^{frac{5}{3}}right))。

所以：带修莫队的渐进时间复杂度为(Oleft(nlogn+n^{frac{5}{3}}right))（视作(n=m)）。

其它例题

CF940F Machine Learning

树上莫队

其实，莫队算法除了序列还可以用于树。复杂度同序列上的莫队（不带修(O(nsqrt{m}+mlogm))，带修(Oleft(nlogn+n^{frac{5}{3}}right))）。

例题

[WC2013]糖果公园

分块方式

这里需要看一道专门为树上莫队设计的题目 [SCOI2005]王室联邦。

用这道题所要求的方式进行分块，并用后文的方式更新答案，就能保证复杂度（复杂度分析见后文）。

那么如何满足每块大小在([B,3B])，块内每个点到核心点路径上的所有点都在块内呢？

这里先提供一种构造方式，再予以证明：

dfs，并创建一个栈，dfs一个点时先记录初始栈顶高度，每dfs完当前节点的一棵子树就判断栈内（相对于刚开始dfs时）新增节点的数量是否(ge B)，是则将栈内所有新增点分为同一块，核心点为当前dfs的点，当前节点结束dfs时将当前节点入栈，整个dfs结束后将栈内所有剩余节点归入已经分好的最后一个块。

如果你看懂了这个方法的话，每块大小>=B是显然的，下面证明为何每块大小(le 3B)：

对于当前节点的每一棵子树：

• 若未被分块的节点数(>B)，那么在dfs这棵子树的根节点时就一定会把这棵子树的一部分分为一块直至这棵子树的剩余节点数(le B)，所以这种情况不存在。

• 若未被分块的节点数(=B)，这些节点一定会和栈中所有节点分为一块，栈中之前还剩([0,B-1])个节点，那么这一块的大小为([B,2B-1])。

• 若未被分块的节点数(<B)，当未被分块的节点数(+)栈中剩余节点数(ge B)时，这一块的大小为([B,2B-1))

• ，否则继续进行下一棵子树。

对于dfs结束后栈内剩余节点，数量一定在([1,B])内，而已经分好的每一块的大小为([B,2B?1])，所以每块的大小都在([B,3B))内。

修改方式

修改，就是由询问((cu,cv)) 更新至询问((tu,tv))。

(T(u,v))表示(u)到(v)的路径上除(lca(u,v))外的所有点构成的集合；

(S(u,v))代表(u)到(v)的路径，(xor)表示集合对称差。

• 两个指针(cu,cv)（相当于序列莫队的(l,r)两个指针），(ans)记录(T(cu,cv))的答案，(mathrm{vis})数组记录每个节点是否在(T(cu,cv))内；
• 由(T(cu,cv))更新至(T(tu,tv))时，将(T(cu,tu))和(T(cv,tv))的(mathrm{vis})分别取反，并相应地更新答案；
• 将答案记录到(mathrm{out})数组（离线后用于输出那个）时对(lca(cu,cv))（此时的(cu,cv)已更新为上一步中的(tu,tv)） 的(mathrm{vis})取反并更新答案，记录完再改回来。

第二步证明如下：

(quad,T(cu,cv) xor T(tu,tv))

(=[S(cu,root) xor S(cv,root)] xor [S(tu,root) xor S(tv,root)])

(=[S(cu,root) xor S(tu,root)] xor [S(cv,root)])

(=T(cu,tu) xor T(cv,tv))

之所以要把(T(cu,tv))转化成(T(cu,tv))，是因为这样的话就能通过对询问排序来保证复杂度。

关于单点修改

树上莫队的单点修改和序列莫队类似，唯一不同就是，修改后是否更新答案通过(mathrm{vis})数组判断。

复杂度分析

（编辑：厦门网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!