主题 作者
- 09
- 14
- 3
- 文章类型
- 完全原创 —— 转载请标注作者
【数据结构】根号系列 2 —— 莫队算法入门
前言
莫队，是由来自国家集训队的莫涛，发明的算法。
本质上，莫队是分块的一个子集，但由于分块本身应用场景复杂（可以解决较复杂的树上、图上问题，或者是非常难的序列问题）
这也导致莫队算法的应用变化多样，不同问题的难度差距巨大。
本文难度与上一篇相比，提升较大，且需要读者掌握序列分块、值域分块，如果觉得有难度，可以跳过这一篇。
本文只介绍最简单的普通莫队，不涉及带修莫队、回滚莫队，树上莫队，莫队二次离线等算法。
引入 - 1
举个简单的 例子：
给你一个长度为 [imath]n[/imath] 的序列，有 [imath]q[/imath] 次询问，每次询问一个区间 [imath][l,r][/imath]
对于每个询问，你需要给出 [imath]a_l+a_{l+1}+\dots + a_{r}[/imath] 的值
很显然，这个问题可以用分块回答，此外，前缀和或树状数据结构也可以解决这个问题。
运用这几个算法，我们可以 在线 地回答这些问题，
在线: 即立刻回答：当给出一个询问 [imath][l,r][/imath]，我立刻求出它的答案，并且输出（你不知道下一个询问会是什么）。
相对地，我们有一个 离线 的概念，
离线：允许你不立刻回答。你可以先得到所有的询问，分析它们的性质（分析后，你可以做一些操作，比如说对这些询问排序），此后一并回答它们。
引入 - 2
普通莫队主要用来解决序列问题，这些问题往往是对区间的询问。
传统意义上的莫队是一种 离线 算法。
依然是前面那题（区间求和）
让我们考虑以下询问 [imath][1,10],[2,11],[3,12],[4,13],[5,14][/imath]
（实际上我可以乱序地给你这些询问，然后我们按左端点升序排序，反正最后处理后，会得到这种顺序）
此后我们可以采用双指针（滑动窗口）的做法。具体地说，设置两个指针（L,R），维护 区间 [L,R] 内元素的和。
每次暴力地移动左指针或右指针到相邻的元素上，同时更新元素和（加、减），直到移动到询问的区间上，那么对应每个询问，元素和自然也就维护好了。
由于这组数据很特殊，我们会发现，左指针、右指针都是单调向右移动的，因此，总复杂度是 [imath]O(n)[/imath] 的
但是考虑下面这组数据，[imath][1,1000],[2,2],[3,1000][/imath]，假设我们继续使用双指针（滑动窗口）
尽管按左端点升序排序后，左端点移动的 总复杂度是 [imath]O(n)[/imath] 的；
但是右端点的复杂度却爆炸了，每次询问的复杂度是 [imath]O(n)[/imath] 的，总复杂度达到了 [imath]O(qn)[/imath] ，这是不可接受的。
如果读者阅读了上一篇文章，一定会意识到，这两个指针之间的复杂度，可以用『不平衡』一词来描述。
实际上，只要两个指针移动的复杂度平衡了，在上文的例子下，不难发现，答案已经维护好了！那么整体的复杂度一定是令人欣喜的（算法复杂度只由指针移动的复杂度决定）！
为此，莫涛发明了一种基于分块的离线算法，名为莫队，来平衡左右指针移动的复杂度。
预处理
假设序列长度为 [imath]n[/imath]，我们将其分为 [imath]\sqrt n[/imath] 个，长度为 [imath]\sqrt n[/imath] 的不相交的块。
此后，我们把每个询问，以询问的左端点为标准，分配到每个块内（可以理解为，对询问进行分组处理）。
举个例子，如果某个询问的左端点在第二个块内，那么这个询问就被分配到了第二个块（第二组）。
分配完成后，我们得到了 [imath]\sqrt n[/imath] 组询问，每组内的询问个数是不确定的。
我们将每组内的询问，按照 右 端点升序排序，不在乎 左 端点（排序后，左端点可以是乱序的）。
分析复杂度
依然是双指针（滑动窗口）的那种做法，它的复杂度现在是多少呢？
左端点
由于按左端点分组，在某一组内，左指针只会在块内移动
那么如果有 [imath]q[/imath] 个询问，左端点每次最多移动 [imath]q \sqrt n[/imath] 次（且每次移动是 [imath]O(1)[/imath] 的）
所以左端点移动的复杂度是 [imath]q \sqrt n[/imath] 的。
右端点
对于右端点，在某一组内，我们由于以右端点为标准，升序排列了所有询问，那么右端点只会单调向右移动。
那么在每个块内，右端点移动的总复杂度是 [imath]O(n)[/imath] 的
而我们一共有 [imath]\sqrt n[/imath] 个块，因此，右端点移动，总的复杂度是 [imath]n \sqrt n[/imath] 的
进一步
实际上 [imath]q \sqrt n[/imath] 和 [imath]n \sqrt n[/imath] 还是有一些细微区别的，如果 [imath]n, q[/imath] 数量级不一样，也会是一种不平衡。
我们可以修改块长，从 [imath]\sqrt n[/imath]，改为 [imath]\dfrac{n}{\sqrt q}[/imath]，
这时，总块数也变为了 [imath]\sqrt q[/imath] ，这是很好理解的。
基于之前的复杂度分析，我们得到了一个复杂度为 [imath]O(n \sqrt q + q)[/imath] 的算法。
有读者可能会疑惑，为什么复杂度内会需要额外写一个 [imath]+q[/imath]。
这是因为每个询问都需要花 [imath]O(1)[/imath] 的时间去回答。即便每个询问都相同，即便你不需要移动指针，算法依然要花费严格下界 [imath]O(q)[/imath] 的时间去回答每个询问。
引入 - 3
好吧，我想，实际上应该还没有到正文。
不难发现，莫队本身就只是一个暴力算法，只不过因为其利用分块，平衡了指针移动的复杂度，导致整个暴力算法的性能表现很好！
值得注意的是，指针移动的复杂度一般要求是 [imath]O(1)[/imath] 的，假设指针移动的复杂度为 [imath]O(a)[/imath]，那么普通莫队的复杂度变为[imath]O(a * n \sqrt q + q)[/imath]。一旦移动指针的复杂度过高，那么算法的效率就会下降很多。
暴力往往比高级数据结构能处理更多问题，维护更多信息，这是因为暴力算法直面信息，直接合并它们。
与之相对地，高级数据结构之所以性能优秀，是因为它们往往通过一些手段避免暴力合并信息 ———— 实际上，很多信息都难以快速合并，不得不暴力。
比如说，每次给你几个集合，让你合并它们。在面对大量的离散数据时，我们往往不得不暴力处理它们（这个例子下，一种优化的方法，是使用 多线程算法 + Cpu 并行指令，来进行暴力合并）。
引入 - 4
给你一个序列 [imath]a[/imath]，值域 [imath]10^5[/imath]，每次询问： 序列区间 [imath][l,r][/imath] 中，有多少元素 [imath]a_i \in [l,r][/imath]
这个问题在允许离线的情况下，可以使用扫描线做到 [imath]O(n\log n)[/imath]，但本文介绍一种『莫队 + 值域分块』的做法。
考虑值域分块这个算法，它通过对『桶』进行分块，实现了 [imath]O(1)[/imath] 加/删一个数，[imath]O(\sqrt n)[/imath] 统计某个值域内的数（即求满足 [imath]a_i \in [l,r][/imath] 的 [imath]a_i[/imath] 个数）。
观察询问，每次它都会给你一个 序列区间 和 值域区间，
假设我们对每个 序列区间 都预处理出一个 『值域分块』，那么时间、空间复杂度都是 [imath]O(n^2)[/imath] 的，性能太糟糕了。
但是注意到，『值域分块』的加数、删数是 [imath]O(1)[/imath] 的，恰好符合莫队的暴力要求（可以通过 [imath]O(1)[/imath] 移动双指针的端点，来维护好某个 序列区间 内的信息）
于是这个问题，在莫队的眼里，就变得很简单了：
1. 离线处理所有询问，把询问按左端点，进行按块分组；同时每组询问内部，按右端点升序。
2. 暴力地跑双指针（滑动窗口），维护存有 [imath]a_l, a_{l+1} \dots a_r[/imath] 信息的『值域分块』。
3. 在跑到位以后（双指针与某个询问的端点重合），在『值域分块』上进行一次查询，得到答案，记录下来。
4. 输出每个询问的答案。
复杂度分析
排序：[imath]O(q\log q)[/imath]
莫队移动指针：[imath]O(n\sqrt q)[/imath]
指针位后查询：[imath]O(q\sqrt n)[/imath]
总复杂度 ~[imath]O(n\sqrt q + q\sqrt n)[/imath]，依然有非常优秀的效率
（当 [imath]n=q=10^5[/imath]，较强的数据也只能让这个算法花费 [imath]300 ms[/imath]，因为莫队算法本身常数较小）
正文
下文的几个经典问题，都是在序列上的问题。
序列长度 [imath]n=10^5[/imath]，询问数量 [imath]q = 10^5[/imath]，耗时 [imath]1s[/imath] 以内
由于难度过大，只选了三个最简单且最具有代表性的进行讲解。
例子 1
约定，[imath]𝑐𝑛𝑡[𝑥][/imath] 表示，数字 [imath]𝑥[/imath] 的出现次数
求某个区间内，所有出现过的数字的 [imath](𝑐𝑛𝑡[𝑥])^2[/imath]之和
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]）
这里就要提到莫队的精髓 ———— 我们总是从前一个区间转移过来：
例如双指针 [imath][l,r][/imath]，移动右指针，变为 [imath][l,r\pm 1][/imath]
实际上，我们总是 『已经维护好了上一个区间的答案』，只需要考虑加/删一个数怎么更新
不难发现，当 [imath]𝑎^2→(𝑎+1)^2[/imath]，后者展开为 [imath]𝑎^2+2𝑎+1[/imath] ，只要我们用桶统计了 [imath]𝑐𝑛𝑡[𝑥][/imath]（即上式的 [imath]a[/imath]），就可以直接更新。
数学地搞搞就更新好了，删除也是同理。
若值域 [imath]\omega[/imath] 为 [imath][1,10^9][/imath]？
离散化。
通过这个例子，希望大家理解，莫队如何进行转移，如何在转移过程中维护信息
例子 2
约定，[imath]𝑔(𝑙, 𝑟 ,𝑥)[/imath] 表示，区间 [imath][l,r][/imath] 内数字 [imath]𝑥[/imath] 的出现次数；
每次询问，给你两个区间，求 [imath]\sum_{x=0}^{\omega}𝑔(𝑙_1, 𝑟_1 ,𝑥)∗𝑔(𝑙_2, 𝑟_2 ,𝑥)[/imath]
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]）
可以把询问差分成四个询问
拿一个询问举例
[imath]𝑔(1, 𝑟_1 ,𝑥 )∗𝑔(1, 𝑟_2 ,𝑥)[/imath]
开两个桶，左指针一个桶，右指针一个桶
移动左指针，数量 [imath]±1[/imath]，对答案的影响是 [imath]± 𝑔(1, 𝑟_2^′ ,𝑥)[/imath] 右指针同理
通过这个例子，希望大家理解，莫队善于维护区间信息，当区间过多，或者不易维护时，我们可以差分地维护（如本题，维护前缀信息）
例子 3
给你一个序列 [imath]𝑎[/imath]，和一个固定值 [imath]𝑘[/imath]
询问：某个区间有多少个子区间的异或值为 [imath]𝑘[/imath]，子区间可以包含自己
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]，包括 [imath]k[/imath]）
『已经维护好了上一个区间的答案』，需要考虑加/删一个数怎么更新
[imath]𝑥[/imath] 在最左或最右，更新的自然是以 [imath]𝑥[/imath] 为端点的区间答案 但是这个区间数量是 [imath]𝑛^2[/imath] 级别的，怎么搞？
实际上，对原序列做一次异或前缀就解决了这个问题
一个子区间 [imath][𝑙, 𝑟][/imath] 的异或和可以表示成 [imath][1, 𝑟] ⊕ [1, 𝑙−1][/imath]，不妨将后面这个式子写成 [imath]x ⊕ a[/imath]
且由 [imath]𝑥 ⊕ 𝑎 = 𝑘[/imath] 可以得到 [imath]𝑥 ⊕ 𝑘 = 𝑎[/imath]，是等价关系
所以只要开一个桶，每次更新统计一下，莫队目前维护的区间里，有多少个 [imath]𝑎[/imath] 即可求出答案
通过这个例子，希望大家理解，莫队的转移往往需要区间信息，而求解区间信息的复杂度过高，往往需要进行一些预处理
总结与思考
莫队是分块的子集，通过离线处理询问，利用分块，优化暴力移动双指针端点的复杂度，实现 [imath]O(n \sqrt q + q)[/imath] 求解区间问题。
实际上，当我们从左到右，不断加入序列上的点，即便单次转移复杂度不是 [imath]O(1)[/imath] 的，只要整体复杂度是 [imath]O(k)[/imath] 的
那么我们就可以实现序列 [imath]n[/imath] -> [imath]k[/imath] 的映射，得到 [imath]O(k \sqrt q + q)[/imath] 的莫队算法
这一做法的理论依据是，我们可以对询问和莫队的 L，R 分别建一个轴，那么每个区间都会变成二维平面内排布的点，
莫队的区间（一个点）通过正交方向的移动（不会斜着走方格的对角线），转移到询问的区间（一个点）
而由于转移的代价是带权的，如果我们建立曼哈顿距离最小生成树，因此将其作为搜索树，一定得到相对良好的复杂度
实际上，这样的做法下，我们消解了单次转移的复杂度为 [imath]O(1)[/imath] 的限制
希望读者喜欢莫队这个暴力算法。
前言
莫队，是由来自国家集训队的莫涛，发明的算法。
本质上，莫队是分块的一个子集，但由于分块本身应用场景复杂（可以解决较复杂的树上、图上问题，或者是非常难的序列问题）
这也导致莫队算法的应用变化多样，不同问题的难度差距巨大。
本文难度与上一篇相比，提升较大，且需要读者掌握序列分块、值域分块，如果觉得有难度，可以跳过这一篇。
本文只介绍最简单的普通莫队，不涉及带修莫队、回滚莫队，树上莫队，莫队二次离线等算法。
引入 - 1
举个简单的 例子：
给你一个长度为 [imath]n[/imath] 的序列，有 [imath]q[/imath] 次询问，每次询问一个区间 [imath][l,r][/imath]
对于每个询问，你需要给出 [imath]a_l+a_{l+1}+\dots + a_{r}[/imath] 的值
很显然，这个问题可以用分块回答，此外，前缀和或树状数据结构也可以解决这个问题。
运用这几个算法，我们可以 在线 地回答这些问题，
在线: 即立刻回答：当给出一个询问 [imath][l,r][/imath]，我立刻求出它的答案，并且输出（你不知道下一个询问会是什么）。
相对地，我们有一个 离线 的概念，
离线：允许你不立刻回答。你可以先得到所有的询问，分析它们的性质（分析后，你可以做一些操作，比如说对这些询问排序），此后一并回答它们。
引入 - 2
普通莫队主要用来解决序列问题，这些问题往往是对区间的询问。
传统意义上的莫队是一种 离线 算法。
依然是前面那题（区间求和）
让我们考虑以下询问 [imath][1,10],[2,11],[3,12],[4,13],[5,14][/imath]
（实际上我可以乱序地给你这些询问，然后我们按左端点升序排序，反正最后处理后，会得到这种顺序）
此后我们可以采用双指针（滑动窗口）的做法。具体地说，设置两个指针（L,R），维护 区间 [L,R] 内元素的和。
每次暴力地移动左指针或右指针到相邻的元素上，同时更新元素和（加、减），直到移动到询问的区间上，那么对应每个询问，元素和自然也就维护好了。
由于这组数据很特殊，我们会发现，左指针、右指针都是单调向右移动的，因此，总复杂度是 [imath]O(n)[/imath] 的
但是考虑下面这组数据，[imath][1,1000],[2,2],[3,1000][/imath]，假设我们继续使用双指针（滑动窗口）
尽管按左端点升序排序后，左端点移动的 总复杂度是 [imath]O(n)[/imath] 的；
但是右端点的复杂度却爆炸了，每次询问的复杂度是 [imath]O(n)[/imath] 的，总复杂度达到了 [imath]O(qn)[/imath] ，这是不可接受的。
如果读者阅读了上一篇文章，一定会意识到，这两个指针之间的复杂度，可以用『不平衡』一词来描述。
实际上，只要两个指针移动的复杂度平衡了，在上文的例子下，不难发现，答案已经维护好了！那么整体的复杂度一定是令人欣喜的（算法复杂度只由指针移动的复杂度决定）！
为此，莫涛发明了一种基于分块的离线算法，名为莫队，来平衡左右指针移动的复杂度。
预处理
假设序列长度为 [imath]n[/imath]，我们将其分为 [imath]\sqrt n[/imath] 个，长度为 [imath]\sqrt n[/imath] 的不相交的块。
此后，我们把每个询问，以询问的左端点为标准，分配到每个块内（可以理解为，对询问进行分组处理）。
举个例子，如果某个询问的左端点在第二个块内，那么这个询问就被分配到了第二个块（第二组）。
分配完成后，我们得到了 [imath]\sqrt n[/imath] 组询问，每组内的询问个数是不确定的。
我们将每组内的询问，按照 右 端点升序排序，不在乎 左 端点（排序后，左端点可以是乱序的）。
分析复杂度
依然是双指针（滑动窗口）的那种做法，它的复杂度现在是多少呢？
左端点
由于按左端点分组，在某一组内，左指针只会在块内移动
那么如果有 [imath]q[/imath] 个询问，左端点每次最多移动 [imath]q \sqrt n[/imath] 次（且每次移动是 [imath]O(1)[/imath] 的）
所以左端点移动的复杂度是 [imath]q \sqrt n[/imath] 的。
右端点
对于右端点，在某一组内，我们由于以右端点为标准，升序排列了所有询问，那么右端点只会单调向右移动。
那么在每个块内，右端点移动的总复杂度是 [imath]O(n)[/imath] 的
而我们一共有 [imath]\sqrt n[/imath] 个块，因此，右端点移动，总的复杂度是 [imath]n \sqrt n[/imath] 的
进一步
实际上 [imath]q \sqrt n[/imath] 和 [imath]n \sqrt n[/imath] 还是有一些细微区别的，如果 [imath]n, q[/imath] 数量级不一样，也会是一种不平衡。
我们可以修改块长，从 [imath]\sqrt n[/imath]，改为 [imath]\dfrac{n}{\sqrt q}[/imath]，
这时，总块数也变为了 [imath]\sqrt q[/imath] ，这是很好理解的。
基于之前的复杂度分析，我们得到了一个复杂度为 [imath]O(n \sqrt q + q)[/imath] 的算法。
有读者可能会疑惑，为什么复杂度内会需要额外写一个 [imath]+q[/imath]。
这是因为每个询问都需要花 [imath]O(1)[/imath] 的时间去回答。即便每个询问都相同，即便你不需要移动指针，算法依然要花费严格下界 [imath]O(q)[/imath] 的时间去回答每个询问。
引入 - 3
好吧，我想，实际上应该还没有到正文。
不难发现，莫队本身就只是一个暴力算法，只不过因为其利用分块，平衡了指针移动的复杂度，导致整个暴力算法的性能表现很好！
值得注意的是，指针移动的复杂度一般要求是 [imath]O(1)[/imath] 的，假设指针移动的复杂度为 [imath]O(a)[/imath]，那么普通莫队的复杂度变为[imath]O(a * n \sqrt q + q)[/imath]。一旦移动指针的复杂度过高，那么算法的效率就会下降很多。
暴力往往比高级数据结构能处理更多问题，维护更多信息，这是因为暴力算法直面信息，直接合并它们。
与之相对地，高级数据结构之所以性能优秀，是因为它们往往通过一些手段避免暴力合并信息 ———— 实际上，很多信息都难以快速合并，不得不暴力。
比如说，每次给你几个集合，让你合并它们。在面对大量的离散数据时，我们往往不得不暴力处理它们（这个例子下，一种优化的方法，是使用 多线程算法 + Cpu 并行指令，来进行暴力合并）。
引入 - 4
给你一个序列 [imath]a[/imath]，值域 [imath]10^5[/imath]，每次询问： 序列区间 [imath][l,r][/imath] 中，有多少元素 [imath]a_i \in [l,r][/imath]
这个问题在允许离线的情况下，可以使用扫描线做到 [imath]O(n\log n)[/imath]，但本文介绍一种『莫队 + 值域分块』的做法。
考虑值域分块这个算法，它通过对『桶』进行分块，实现了 [imath]O(1)[/imath] 加/删一个数，[imath]O(\sqrt n)[/imath] 统计某个值域内的数（即求满足 [imath]a_i \in [l,r][/imath] 的 [imath]a_i[/imath] 个数）。
观察询问，每次它都会给你一个 序列区间 和 值域区间，
假设我们对每个 序列区间 都预处理出一个 『值域分块』，那么时间、空间复杂度都是 [imath]O(n^2)[/imath] 的，性能太糟糕了。
但是注意到，『值域分块』的加数、删数是 [imath]O(1)[/imath] 的，恰好符合莫队的暴力要求（可以通过 [imath]O(1)[/imath] 移动双指针的端点，来维护好某个 序列区间 内的信息）
于是这个问题，在莫队的眼里，就变得很简单了：
1. 离线处理所有询问，把询问按左端点，进行按块分组；同时每组询问内部，按右端点升序。
2. 暴力地跑双指针（滑动窗口），维护存有 [imath]a_l, a_{l+1} \dots a_r[/imath] 信息的『值域分块』。
3. 在跑到位以后（双指针与某个询问的端点重合），在『值域分块』上进行一次查询，得到答案，记录下来。
4. 输出每个询问的答案。
复杂度分析
排序：[imath]O(q\log q)[/imath]
莫队移动指针：[imath]O(n\sqrt q)[/imath]
指针位后查询：[imath]O(q\sqrt n)[/imath]
总复杂度 ~[imath]O(n\sqrt q + q\sqrt n)[/imath]，依然有非常优秀的效率
（当 [imath]n=q=10^5[/imath]，较强的数据也只能让这个算法花费 [imath]300 ms[/imath]，因为莫队算法本身常数较小）
正文
下文的几个经典问题，都是在序列上的问题。
序列长度 [imath]n=10^5[/imath]，询问数量 [imath]q = 10^5[/imath]，耗时 [imath]1s[/imath] 以内
由于难度过大，只选了三个最简单且最具有代表性的进行讲解。
例子 1
约定，[imath]𝑐𝑛𝑡[𝑥][/imath] 表示，数字 [imath]𝑥[/imath] 的出现次数
求某个区间内，所有出现过的数字的 [imath](𝑐𝑛𝑡[𝑥])^2[/imath]之和
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]）
这里就要提到莫队的精髓 ———— 我们总是从前一个区间转移过来：
例如双指针 [imath][l,r][/imath]，移动右指针，变为 [imath][l,r\pm 1][/imath]
实际上，我们总是 『已经维护好了上一个区间的答案』，只需要考虑加/删一个数怎么更新
不难发现，当 [imath]𝑎^2→(𝑎+1)^2[/imath]，后者展开为 [imath]𝑎^2+2𝑎+1[/imath] ，只要我们用桶统计了 [imath]𝑐𝑛𝑡[𝑥][/imath]（即上式的 [imath]a[/imath]），就可以直接更新。
数学地搞搞就更新好了，删除也是同理。
若值域 [imath]\omega[/imath] 为 [imath][1,10^9][/imath]？
离散化。
通过这个例子，希望大家理解，莫队如何进行转移，如何在转移过程中维护信息
例子 2
约定，[imath]𝑔(𝑙, 𝑟 ,𝑥)[/imath] 表示，区间 [imath][l,r][/imath] 内数字 [imath]𝑥[/imath] 的出现次数；
每次询问，给你两个区间，求 [imath]\sum_{x=0}^{\omega}𝑔(𝑙_1, 𝑟_1 ,𝑥)∗𝑔(𝑙_2, 𝑟_2 ,𝑥)[/imath]
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]）
可以把询问差分成四个询问
拿一个询问举例
[imath]𝑔(1, 𝑟_1 ,𝑥 )∗𝑔(1, 𝑟_2 ,𝑥)[/imath]
开两个桶，左指针一个桶，右指针一个桶
移动左指针，数量 [imath]±1[/imath]，对答案的影响是 [imath]± 𝑔(1, 𝑟_2^′ ,𝑥)[/imath] 右指针同理
通过这个例子，希望大家理解，莫队善于维护区间信息，当区间过多，或者不易维护时，我们可以差分地维护（如本题，维护前缀信息）
例子 3
给你一个序列 [imath]𝑎[/imath]，和一个固定值 [imath]𝑘[/imath]
询问：某个区间有多少个子区间的异或值为 [imath]𝑘[/imath]，子区间可以包含自己
（值域 [imath]\omega[/imath] 为 [imath][1,10^5][/imath]，包括 [imath]k[/imath]）
『已经维护好了上一个区间的答案』，需要考虑加/删一个数怎么更新
[imath]𝑥[/imath] 在最左或最右，更新的自然是以 [imath]𝑥[/imath] 为端点的区间答案 但是这个区间数量是 [imath]𝑛^2[/imath] 级别的，怎么搞？
实际上，对原序列做一次异或前缀就解决了这个问题
一个子区间 [imath][𝑙, 𝑟][/imath] 的异或和可以表示成 [imath][1, 𝑟] ⊕ [1, 𝑙−1][/imath]，不妨将后面这个式子写成 [imath]x ⊕ a[/imath]
且由 [imath]𝑥 ⊕ 𝑎 = 𝑘[/imath] 可以得到 [imath]𝑥 ⊕ 𝑘 = 𝑎[/imath]，是等价关系
所以只要开一个桶，每次更新统计一下，莫队目前维护的区间里，有多少个 [imath]𝑎[/imath] 即可求出答案
通过这个例子，希望大家理解，莫队的转移往往需要区间信息，而求解区间信息的复杂度过高，往往需要进行一些预处理
总结与思考
莫队是分块的子集，通过离线处理询问，利用分块，优化暴力移动双指针端点的复杂度，实现 [imath]O(n \sqrt q + q)[/imath] 求解区间问题。
实际上，当我们从左到右，不断加入序列上的点，即便单次转移复杂度不是 [imath]O(1)[/imath] 的，只要整体复杂度是 [imath]O(k)[/imath] 的
那么我们就可以实现序列 [imath]n[/imath] -> [imath]k[/imath] 的映射，得到 [imath]O(k \sqrt q + q)[/imath] 的莫队算法
这一做法的理论依据是，我们可以对询问和莫队的 L，R 分别建一个轴，那么每个区间都会变成二维平面内排布的点，
莫队的区间（一个点）通过正交方向的移动（不会斜着走方格的对角线），转移到询问的区间（一个点）
而由于转移的代价是带权的，如果我们建立曼哈顿距离最小生成树，因此将其作为搜索树，一定得到相对良好的复杂度
实际上，这样的做法下，我们消解了单次转移的复杂度为 [imath]O(1)[/imath] 的限制
希望读者喜欢莫队这个暴力算法。
最后编辑：