1. 引言莫队算法Mo’s Algorithm是一种用于高效处理离线区间查询问题的优雅算法。它由莫涛在 2009 年提出通过巧妙地调整查询顺序将时间复杂度从 O(n²) 优化至 O(n√n) 级别成为解决大量静态区间查询问题的利器。本文将系统性地介绍基础莫队算法的核心思想、实现步骤、复杂度分析并通过经典例题如区间内不同数字的个数进行实战演练帮助读者彻底掌握这一算法。2. 算法核心思想莫队算法的核心在于“分块”与“离线处理”。2.1 问题模型我们通常面对的问题是给定一个长度为 n 的序列 a[1…n]以及 m 个离线查询每个查询询问区间 [l, r] 的某个属性如不同元素个数、区间和、众数等。我们需要高效地回答所有查询。2.2 暴力法的瓶颈最直接的方法是对于每个查询扫描整个区间 [l, r] 进行计算。总时间复杂度为 O(mn)在 n 和 m 达到 10⁵ 级别时完全不可行。2.3 莫队的优化思路莫队算法观察到相邻查询的区间往往有大量重叠部分。如果我们能从一个查询的答案 [l, r] 快速推导出下一个查询的答案 [l’, r’]就能避免大量重复计算。具体做法将序列分成大小为 B 的块通常 B √n。将所有查询按左端点所在的块编号为第一关键字排序右端点为第二关键字排序。按此顺序依次处理查询通过移动当前区间的左右指针 l, r 来“滑”到目标区间并维护当前答案。3. 算法实现步骤3.1 数据结构准备structQuery{intl,r,id;// 查询区间 [l, r] 和查询编号};intn,m;// 序列长度查询个数inta[MAXN];// 原序列Query q[MAXM];// 查询数组intblock_size;// 块大小intans[MAXM];// 存储每个查询的答案intcur_ans;// 当前区间 [cur_l, cur_r] 的答案intcnt[MAXV];// 计数数组用于维护当前区间内每个值的出现次数以统计不同数字为例3.2 排序函数boolcmp(constQuerya,constQueryb){// 按左端点所在块排序块号相同则按右端点排序intblock_aa.l/block_size;intblock_bb.l/block_size;if(block_a!block_b)returnblock_ablock_b;// 奇偶化排序优化奇数块右端点升序偶数块右端点降序减少指针移动return(block_a1)?(a.rb.r):(a.rb.r);}3.3 区间移动操作以统计不同数字个数为例voidadd(intpos){// 将位置 pos 的元素加入当前区间if(cnt[a[pos]]0)cur_ans;// 之前没出现过不同数字数1cnt[a[pos]];}voiddel(intpos){// 将位置 pos 的元素从当前区间移除cnt[a[pos]]--;if(cnt[a[pos]]0)cur_ans--;// 该数字出现次数归零不同数字数-1}3.4 主算法流程voidmo(){block_sizesqrt(n);// 设置块大小sort(q,qm,cmp);// 对查询排序intcur_l1,cur_r0;// 当前维护的区间初始为空区间 [1, 0]cur_ans0;for(inti0;im;i){intlq[i].l,rq[i].r;// 移动左指针 cur_l 到目标 lwhile(cur_ll)add(--cur_l);while(cur_ll)del(cur_l);// 移动右指针 cur_r 到目标 rwhile(cur_rr)add(cur_r);while(cur_rr)del(cur_r--);ans[q[i].id]cur_ans;// 记录答案}}4. 复杂度分析4.1 时间复杂度左指针移动对于每个查询左指针最多移动 O(√n) 次因为左端点在同一个块内。共有 m 个查询所以总移动次数为 O(m√n)。右指针移动对于每个块右指针单调移动总移动次数为 O(n)。共有 O(√n) 个块所以总移动次数为 O(n√n)。总复杂度O((nm)√n)。当 n 和 m 同阶时约为 O(n√n)。4.2 空间复杂度需要存储原序列、查询和答案数组以及辅助计数数组总空间复杂度为 O(n m max_value_range)。5. 经典例题区间不同数字个数问题描述给定一个长度为 n 的序列m 次询问每次询问区间 [l, r] 内有多少个不同的数字。解决方案这正是基础莫队的模板题。我们使用上面给出的代码框架add和del函数维护当前区间内每个数字的出现次数cnt[]以及不同数字的个数cur_ans。完整代码示例#includebits/stdc.husingnamespacestd;constintMAXN30005;constintMAXM200005;constintMAXV1000005;intn,m,block_size;inta[MAXN],ans[MAXM],cnt[MAXV],cur_ans;structQuery{intl,r,id;}q[MAXM];boolcmp(constQuerya,constQueryb){intblock_aa.l/block_size;intblock_bb.l/block_size;if(block_a!block_b)returnblock_ablock_b;return(block_a1)?(a.rb.r):(a.rb.r);}voidadd(intpos){if(cnt[a[pos]]0)cur_ans;cnt[a[pos]];}voiddel(intpos){cnt[a[pos]]--;if(cnt[a[pos]]0)cur_ans--;}intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d,a[i]);scanf(%d,m);for(inti0;im;i){scanf(%d %d,q[i].l,q[i].r);q[i].idi;}block_sizesqrt(n);sort(q,qm,cmp);intcur_l1,cur_r0;cur_ans0;for(inti0;im;i){intlq[i].l,rq[i].r;while(cur_ll)add(--cur_l);while(cur_ll)del(cur_l);while(cur_rr)add(cur_r);while(cur_rr)del(cur_r--);ans[q[i].id]cur_ans;}for(inti0;im;i)printf(%d\n,ans[i]);return0;}