“线段树用递归层次组织可合并摘要，树状数组擅长可逆的前缀聚合；排序块提供的是容易局部重建的一层结构。若请求必须立刻回答，本页实现可以直接工作。若请求全部已知且数组不变，莫队算法能重排窗口，以频…”
形式陈述
允许改变计算次序，保留输出身份
输入是一份固定的数组A[0..n)和q个已知查询Qᵢ=[lᵢ,rᵢ)。每个查询带有原始编号i。莫队算法重排这些查询的执行次序，用一个当前窗口[L,R)增删端点元素，更新某种统计，最后按原编号返回答案。这里不允许穿插修改A，也不允许下一次查询由尚未返回的答案决定。[1, PDF pp.28–38；2, PDF pp.103–115]
所需接口是四种合法转移：加入左端、加入右端、删除左端、删除右端，以及读取当前答案。这四种操作不一定相同。对只依赖频次的统计，左右端使用同一加法和同一减法即可；若统计依赖顺序，必须分别证明四种更新正确。
取块长1≤B≤n，按 (floor(lᵢ/B), rᵢ, i) 升序排序非空查询。空查询直接返回空窗口的统计，不参加排序；n=0时全部合法查询都是空的。本页同时求不同值数D和频次平方和F=Σₓcₓ²，空窗口二者均为零。
直觉
合并两个答案很难，移动一步却容易
若左段不同值数为2，右段也为2，并段可能有2、3或4种值；两个数字不足以合并。莫队保留每个值的频次cₓ，不从两个摘要拼答案，而是把上一个完整窗口改成下一个窗口。
加入值x时，旧频次为c：若c=0则D加一，F增加(c+1)²−c²=2c+1，再将频次加一。删除时旧频次c必须正：若c=1则D减一，F减去c²−(c−1)²=2c−1，再将频次减一。所有其他值不变，所以这两个更新直接保持统计定义。
先扩展，再收缩
从[L,R)转到[l,r)，可采用以下固定次序：
text
当 L > l：--L，加入 A[L]
当 R < r：加入 A[R]，++R
当 L < l：删除 A[L]，++L
当 R > r：--R，删除 A[R]先扩展使当前窗口包含旧窗口和目标窗口的并区间，再删去目标之外的两侧。于是每次删除的下标确实属于当前窗口，每次加入的下标此前在窗口之外；这一点在两窗口不相交时也成立。
从空窗[0,0)去[4,6)，若先执行“L<4就删除A[L]”，第一次便删除了从未加入的元素。正确顺序先扩展到[0,6)，再删掉下标0到3。频次非负是必须维持的状态条件，不能只盼最后的加减恰好抵消。
左端分块限制往返
算法利用平方根分解的块长取舍，但分组对象是查询的左端点。在同一左端块里，L的目标位置相差不到B；按r排序后，R只向右走。换到下一块时，R可以回到较小位置，但这种重新开始至多发生⌈n/B⌉次。
可以让相邻块的r升序、降序交替，以减少实际往返；本页实现固定升序，证明和手算都按这一版本进行，不把常数优化混入正确性条件。
例子与边界
七个查询，六次窗口转换
仍取A=[3,1,3,2,1,4,2,3]，B=3。原编号和答案如下，括号内依次是D、F：
| 编号 | 区间 | 答案 |
|---|---|---|
| 0 | [2,7) | (4,7) |
| 1 | [0,4) | (3,6) |
| 2 | [4,8) | (4,4) |
| 3 | [1,6) | (4,7) |
| 4 | [3,3) | (0,0) |
| 5 | [0,8) | (4,18) |
| 6 | [3,5) | (2,2) |
非空查询的实际顺序为1、3、0、5、6、2。例如[2,7)到[0,8)先加入下标1、0，再加入7；值3最终出现三次，值1、2各两次，值4一次，所以F=9+4+4+1=18。
从[0,8)转到[3,5)，先删左侧0、1、2，再删右侧7、6、5，剩下[2,1]。这一轮右端确实向左退，因为左端从第0块进入了第1块。答案仍写回编号6的位置，而不能按执行顺序交给调用者。
能增加，不一定能删除
若只维护窗口最小值，一个新元素可以常数时间加入，但删除唯一最小值后并不知道次小值。这样的状态还不满足莫队接口；需要额外结构，并把它的更新成本代入总界。保存全频次也有值域成本：附件先按值和位置排序进行坐标压缩，给相等值同一密集编号，再用数组保存频次。
原数组若在两个查询之间改变，重排查询就会改变问题本身。带修改莫队要把修改时间加入状态并支持前进和撤回，这是额外接口，本页不承诺。若l或r由前次答案解码得到，批量排序前连真实查询都不知道，也不能直接应用。
推论与应用
对两个指针分别记账
同一左端块内，每次L移动少于B，共O(qB)。跨块移动的块编号只增加，跳过的整块长度总和O(n)，而各次落点的块内偏移可并入O(qB)。故L总移动O(qB+n)。每块内R单调，初次定位及跨块回退各至多n，共O(n⌈n/B⌉)。
若每次增删和读答案均O(1)，计入比较排序、压缩和结果数组后，总成本为
工作空间O(n+q)。n=0时只需校验并返回q份空答案；上式的分块推导限n≥1。一般转移成本若为C，应将指针移动项乘C；读取一个很长的答案还要另计输出大小。
平衡qB和n²/B得到B约为n/√q，而不是对任何q都固定√n。附件使用整数平方根求近似值，并夹到[1,n]；q=0时不进行窗口移动。q远大于n²时B仍不能小于一，排序和写出q份答案也不可能消失。
上述界按整数装入机器字的RAM计算。附件 audit=True 在每次移动后重新扫描窗口核对频次，是测试用的慢检查；正式成本针对关闭该选项的核心。开启 trace 每个已处理查询记录常数大小轨迹，额外O(q)时间和空间。
同值配对概率是一项可推导的输出
长度m≥2的窗口中，两个不同位置的无序同值对数为Σₓcₓ(cₓ−1)/2=(F−m)/2。因此均匀抽两个不同位置时，同值概率为(F−m)/(m(m−1))。在查询0的长度5窗口里，F=7，恰有一对相等位置，概率1/10；m<2时没有这种抽样实验，不能除以零。
批量查询终结任务要求从频次更新、合法窗口和原查询ID三个层面核对结果，再将一条点赋值加入输入，说明为何必须改用在线结构或带时间的离线模型。