分块与莫队：离线区间问题的常见技巧
学到区间结构这里，很多人会自然把注意力放在线段树、树状数组这些“动态在线维护”结构上。但并不是所有区间问题都必须在线处理。有一类问题很有代表性：
- 所有查询在一开始就已经给出；
- 不一定要求实时回答；
- 重点在于减少整体重复计算。
这种场景下，离线算法就会变得非常有吸引力。分块和莫队，正是这类思路中最经典的两种技巧。它们并不是在结构能力上硬拼线段树，而是换了一个视角：
如果我能自由安排处理顺序，能不能让相邻查询之间共享更多中间状态，从而降低总成本？
这类思路非常重要，因为它提醒我们：数据结构优化不一定总是“设计一棵更强的树”，有时换一种处理顺序，本身就是算法优化。
一、什么是分块思想
分块可以先理解成：
把原始序列按大小相近的若干块划分开来，对每块维护额外信息，从而在查询和修改时减少全量扫描。
例如把长度为 n 的数组分成大约 √n 块：
- 每块长度大约也是
√n； - 块内元素较少，暴力处理可接受；
- 块与块之间可以借助块级信息快速处理。
这是一种非常经典的“分层处理”思路：
- 块内细节保留；
- 块间信息摘要化。
二、为什么分块常常和 √n 联系在一起
因为很多场景下，把：
- 块数设为
√n； - 块长也控制在
√n左右；
会让：
- 每次跨完整块的处理成本；
- 每次处理边缘残块的成本；
达到一个比较平衡的折中。
这不一定是唯一选择，但作为经典经验非常常见，所以很多分块结构复杂度里会出现 O(√n) 量级。
三、分块适合解决什么问题
典型适合：
- 区间求和、区间最值等可分块统计问题；
- 带有少量修改的区间查询；
- 需要在块级别维护统计量的问题；
- 某些可以“整块处理 + 边缘暴力”的题。
这类问题的共同味道是：
- 全暴力太慢；
- 但上重型结构又未必必要；
- 而且问题常常天然支持“分块摘要”。
四、什么是莫队算法
莫队可以理解成：
对一批离线区间查询重新排序，使得处理相邻查询时，左右端点移动总量尽量小，从而复用当前区间状态。
它通常用在这样的情形：
- 查询很多；
- 没有修改，或者修改较少的离线问题；
- 某个区间答案可以通过“左右端点扩缩”增量维护出来。
这是一种特别有代表性的离线思想：
- 不直接一个个按原顺序答；
- 而是先排序问题本身；
- 再把“多个查询一起看”当成一个整体优化对象。
五、莫队为什么要排序查询
因为如果区间查询原顺序很乱，那么：
- 上一个区间在左边；
- 下一个区间又跳到很远的地方；
- 每次都要大幅重建统计状态；
- 总成本会很高。
于是莫队会通常按：
- 左端点所在块编号；
- 再按右端点排序；
让相邻查询尽可能“靠得近”。
这样处理时，当前维护区间只需要小幅移动，就能从一个查询过渡到下一个。
六、莫队的核心操作是什么
莫队真正依赖的不是排序本身，而是：
你是否能在左右端点每移动一步时，快速地增删一个元素，并更新当前答案。
也就是说，它通常需要你提供两种能力：
add(x)：某元素进入当前区间时，如何更新答案；remove(x)：某元素离开当前区间时，如何更新答案。
如果这两步都能很快完成，那么整个莫队过程就会非常有效。
七、莫队适合什么类型的题
最经典的是：
- 区间不同元素个数；
- 区间众数相关统计；
- 区间频率函数值；
- 区间某类计数问题。
共同特点通常是：
- 直接求单个查询也许不难；
- 但对大量查询重复做会很慢；
- 同时答案可以通过“加一个数 / 删一个数”来增量维护。
也就是说，莫队特别擅长那种：
单个区间统计本身有点复杂，但区间滑动一步时更新很便宜。
八、莫队和线段树 / 树状数组有什么本质区别
1. 线段树 / 树状数组
- 强调在线维护；
- 每来一个查询立即回答；
- 更像实时数据结构。
2. 莫队
- 强调离线处理；
- 先拿到所有查询再统一排序；
- 更像批量优化处理顺序。
所以二者不是谁更高级，而是适用前提不同：
- 在线问题，莫队不适合；
- 离线批量问题，莫队有时会非常强。
九、为什么说莫队是“顺序优化”而不是“结构增强”
这点特别值得体会。
线段树和树状数组是在增强结构本身；
而莫队更像是在说：
- 结构不一定变；
- 我换个查询顺序；
- 就能把重复劳动压下来。
这种思路很有启发，因为它告诉我们：
优化不一定来自更复杂的数据结构，也可能来自更聪明的处理调度。
十、学习分块与莫队时最容易踩的坑
1. 不区分在线和离线
如果题目要求实时回答，莫队通常就不合适。
2. 以为莫队只是一种排序技巧
真正关键的是是否能高效增删元素维护答案。
3. 分块只背 √n，不理解为什么这样划分
本质上是为了平衡块内暴力和块间摘要的代价。
4. 把莫队当作万能区间算法
它适合的是一类特定离线问题，不是所有区间查询都该上莫队。
总结
分块与莫队的重要性，不只是因为它们是竞赛技巧，而是因为它们特别能训练你从“处理顺序”和“信息层次”两个角度重新看区间问题。真正值得先建立起来的，是这些核心认识：
- 分块通过把序列划成若干块，建立块级摘要，从而减少区间处理代价；
- 莫队通过离线重排查询顺序，尽量减少相邻查询之间状态变化量；
- 莫队的核心不只是排序，而是能否支持快速 add/remove 增量维护；
- 它们都体现了一个重要思想：不是所有优化都来自更强结构，很多优化来自更聪明的组织方式；
- 在线实时问题更偏向线段树 / 树状数组，离线批量问题则可能更适合莫队；
- 真正学会这部分，不是记住块长和排序规则，而是能看出“这个问题是不是适合通过重新组织查询来省掉大量重复工作”。
把这一篇理解透之后，后面再去学 Treap、Splay 或外部存储结构时，你会更容易意识到：数据结构的世界并不只是“造一个结构”，很多时候还包括“怎样调度问题，让结构更好发挥”。
参考资源：