分块算法与莫队算法：区间问题的高效解法

1. 分块算法区间问题的暴力美学分块算法本质上是一种优雅的暴力它将整个数据序列分割成若干个大小相等的块最后一个块可能不满通过对这些块的整体操作与块内暴力操作相结合达到平衡时间复杂度的目的。这种思想在计算机科学中被称为分而治之的经典应用。假设我们有一个长度为n的数组将其分成√n个块每个块的大小约为√n。这种分块方式不是随意的——它使得单次操作的时间复杂度能够控制在O(√n)级别。例如当我们需要进行区间修改时对于完全包含在查询区间内的整块我们可以直接对块进行整体标记时间复杂度O(1)对于部分包含在查询区间内的块我们暴力修改其中的元素时间复杂度O(√n)这种整块快速处理零散块暴力处理的模式使得分块算法在解决区间问题时展现出独特的优势。与线段树等更复杂的数据结构相比分块算法实现简单直观特别适合算法竞赛中的快速编码场景。实际应用中块大小的选择并非固定为√n。当操作次数与数据规模不同时可以通过调整块大小来优化性能。例如当修改操作远多于查询操作时适当增大块大小可能更有利。2. 分块算法的典型应用场景2.1 区间加法与单点查询考虑这样一个基础问题需要对数组进行多次区间加法操作然后查询单个元素的值。使用分块算法时我们为每个块维护一个加法标记add表示该块整体被加了多少。当执行区间加法操作[l,r]时处理左端不完整的块暴力遍历该块中位于[l,r]内的元素直接加上值处理中间完整的块直接修改这些块的add标记处理右端不完整的块同左端处理方式查询位置i的值时只需返回原始值加上所在块的add标记。这种实现方式下区间修改和单点查询的时间复杂度都是O(√n)。2.2 区间查询与单点修改另一种常见场景是频繁的单点修改配合区间查询。例如我们需要维护一个数组支持将某个位置的值修改为v查询区间[l,r]的和分块解法是为每个块维护一个sum值表示块内元素的和。当修改位置i的值为v时找到i所在的块更新该块的sum值sum sum - old_value v更新数组中的值查询区间和时初始化结果为0处理左端不完整块暴力累加区间内元素处理中间完整块直接加上这些块的sum值处理右端不完整块暴力累加区间内元素这种实现同样保证了O(√n)的时间复杂度且实现比线段树等结构简单得多。3. 从分块到莫队查询优化的艺术莫队算法可以看作是对分块思想的创造性发展它专门解决一类特殊的区间查询问题。莫队算法的核心在于将查询离线处理并通过对查询顺序的精心安排来降低时间复杂度。3.1 莫队算法的适用条件莫队算法适用于满足以下条件的问题静态数据只有查询没有修改或者修改操作可以特殊处理区间可扩展性已知[L,R]的答案可以快速计算出[L±1,R]和[L,R±1]的答案允许离线处理所有查询可以预先获取不需要实时响应这类问题在算法竞赛中非常常见比如区间内不同数字的个数、区间众数、区间mex值等。3.2 基本莫队算法的工作原理基本莫队算法的步骤如下将序列分块块大小为√n对所有查询进行排序先按左端点所在的块号排序块号相同则按右端点排序初始化当前区间为[0,-1]空区间依次处理每个查询通过移动当前区间的左右端点来得到新查询区间的答案这种排序方式的关键在于左端点每次移动不超过√n距离因为在一个块内右端点在同一块内是单调递增的总共移动不超过n次跨块时右端点可能大幅移动但最多发生√n次因此总时间复杂度为O(n√n)这在n1e5时是完全可接受的。4. 莫队算法的实现细节与优化4.1 基础实现模板以下是莫队算法的C实现框架int block_size; // 一般为sqrt(n) struct Query { int l, r, idx; bool operator(Query other) const { if (l / block_size ! other.l / block_size) return l other.l; return (l / block_size 1) ? (r other.r) : (r other.r); } }; vectorint mo_s_algorithm(vectorQuery queries) { vectorint answers(queries.size()); sort(queries.begin(), queries.end()); int cur_l 0, cur_r -1; for (Query q : queries) { while (cur_l q.l) { cur_l--; add(cur_l); } while (cur_r q.r) { cur_r; add(cur_r); } while (cur_l q.l) { remove(cur_l); cur_l; } while (cur_r q.r) { remove(cur_r); cur_r--; } answers[q.idx] get_answer(); } return answers; }4.2 奇偶性排序优化注意到上述代码中operator的实现有一个技巧当左端点在同一块时奇数块的查询按右端点升序排序偶数块则降序排序。这种之字形排序可以避免右端点在换块时的大幅度回移在实际应用中能显著减少操作次数。4.3 带修改的莫队算法对于允许少量修改操作的问题我们可以扩展莫队算法。此时需要记录每个查询前执行的修改次数并在处理查询时同步进行或回滚修改。这种情况下块大小通常取n^(2/3)时间复杂度为O(n^(5/3))。5. 莫队算法实战区间不同数字计数让我们通过一个经典问题来具体理解莫队算法的应用给定一个数组多次查询区间[l,r]内不同数字的个数。5.1 问题分析这个问题满足莫队算法的适用条件静态数据假设没有修改区间可扩展增加一个元素时如果该元素之前出现次数为0则不同数字数1删除一个元素时如果该元素之后出现次数变为0则不同数字数-1允许离线处理5.2 具体实现#include bits/stdc.h using namespace std; int block_size; int cnt[1000005]; // 假设元素值范围是[0,1e6] int res 0; struct Query { int l, r, idx; bool operator(Query other) const { if (l / block_size ! other.l / block_size) return l other.l; return (l / block_size 1) ? (r other.r) : (r other.r); } }; void add(int idx, vectorint a) { if (cnt[a[idx]] 0) res; cnt[a[idx]]; } void remove(int idx, vectorint a) { cnt[a[idx]]--; if (cnt[a[idx]] 0) res--; } vectorint mo_s_algorithm(vectorint a, vectorQuery queries) { vectorint answers(queries.size()); sort(queries.begin(), queries.end()); int cur_l 0, cur_r -1; for (Query q : queries) { while (cur_l q.l) { cur_l--; add(cur_l, a); } while (cur_r q.r) { cur_r; add(cur_r, a); } while (cur_l q.l) { remove(cur_l, a); cur_l; } while (cur_r q.r) { remove(cur_r, a); cur_r--; } answers[q.idx] res; } return answers; } int main() { int n; cin n; block_size sqrt(n); vectorint a(n); for (int i 0; i n; i) cin a[i]; int q; cin q; vectorQuery queries(q); for (int i 0; i q; i) { cin queries[i].l queries[i].r; queries[i].l--; queries[i].r--; // 转换为0-based queries[i].idx i; } vectorint ans mo_s_algorithm(a, queries); for (int x : ans) cout x \n; return 0; }5.3 性能分析对于n个元素和q次查询该算法的时间复杂度为O((nq)√n)。在实际测试中这个算法可以在1秒内处理n,q1e5规模的问题完全满足竞赛需求。6. 分块与莫队的对比与选择6.1 适用场景对比特性分块算法莫队算法修改操作支持各种区间修改通常不支持或有限支持查询类型支持各种区间查询需要满足区间可扩展性处理方式在线处理离线处理时间复杂度通常O(√n)每次操作通常O(n√n)预处理所有查询实现难度中等相对简单扩展性容易扩展到高维主要针对一维区间问题6.2 选择建议当问题需要支持复杂的区间修改操作时分块算法是更好的选择当问题只有查询或很少修改且满足区间可扩展性时莫队算法通常更高效在算法竞赛中如果时间紧迫莫队算法通常更容易快速实现且不易出错对于特殊问题如区间众数莫队算法可能是少数可行的解决方案之一7. 高级变种与扩展应用7.1 回滚莫队对于某些问题add操作容易实现但remove操作难以实现如区间最大值查询可以使用回滚莫队。其核心思想是按左端点所在块分组处理查询对于每组查询右端点单调递增左端点每次从块的最右端开始向左扩展处理完查询后回滚到块的最右端这种变种保持了O(n√n)的时间复杂度同时避免了难以实现的remove操作。7.2 树上莫队莫队算法可以扩展到树结构上处理子树查询或路径查询。常用的方法是将树转为欧拉序或莫比乌斯序然后在这些序列上应用类似一维莫队的算法。7.3 多指针莫队对于需要维护多个区间的问题如计算区间相似度可以使用多个指针同时移动的扩展莫队算法。这种变种虽然时间复杂度更高但在某些特殊问题中非常有效。8. 实战经验与优化技巧块大小选择理论最优值(√n)不一定是最佳实践值。对于不同问题可以通过微调块大小如n/√q来获得更好的常数因子预处理加速对于复杂的add/remove操作可以预处理常用计算结果来加速内存访问优化合理安排数据结构的内存布局提高缓存命中率输入输出优化在处理大规模数据时使用快速的IO方法可以显著提升整体性能常数优化内联关键函数、减少条件判断等底层优化对莫队算法非常有效在实际比赛中我遇到过多次因为块大小选择不当导致TLE时间限制 exceeded的情况。后来发现对于n1e5的问题块大小设为400-600往往比严格的√n≈317表现更好这是因为现代CPU的缓存行为对算法实际性能有显著影响。