莫队算法概述基本概念离线算法、分块思想、处理区间查询问题核心思想通过调整查询顺序减少时间复杂度适用场景静态区间查询如区间众数、区间不同元素计数标准莫队算法算法流程分块排序、双指针移动、维护答案时间复杂度分析$O(n\sqrt{n})$ 的推导与证明代码模板示例伪代码struct Query { int l, r, id; }; void add(int x) { /* 更新当前区间状态 */ } void del(int x) { /* 回退当前区间状态 */ } void solve() { sort(queries); // 按分块排序 int l 1, r 0; for (auto q : queries) { while (l q.l) add(--l); while (r q.r) add(r); // 同理处理删除操作 ans[q.id] current_ans; } }莫队算法的优化变种带修莫队支持单点修改时间轴引入三维查询 $(l, r, t)$ 的排序策略分块大小调整$O(n^{\frac{2}{3}})$ 复杂度的优化回滚莫队处理增/删不对称问题应用场景如区间最值问题实现方式暂存历史状态按需回滚树上莫队处理树形结构查询欧拉序转换将树转为线性序列路径查询处理LCA 特判与区间映射性能优化技巧奇偶性排序减少指针移动距离分块大小选择理论最优值 $O(\frac{n}{\sqrt{m}})$ 的实践调整常数优化内联函数、预处理块编号