莫队算法详解与应用
基础概念
莫队算法是一种经典的离线处理技术，主要用于解决区间查询类问题。其核心思想是通过合理安排查询顺序，使得相邻查询之间的状态转移尽可能高效。
该算法要求能够以 O(1) 时间复杂度从区间 [l,r] 扩展到 [l±1,r] 或 [l,r±1]。在理想情况下，可以在 O(n√n) 时间内完成所有查询。
标准实现方法
实现流程如下：
- 将所有查询请求按离线方式处理
- 根据左端点所属区块作为主键，右端点作为次键进行排序
- 依次处理每个查询，通过指针移动维护当前区间状态
复杂度分析
在最坏情况下，每次左指针最多移动 √n 步，右指针最多移动 n 步。由于总共有 √n 个区块，整体复杂度为 O(n√n)。
提示：调整区块大小可能会带来性能提升。
经典例题解析
以区间不同元素计数为例，关键在于维护每个元素出现次数的平方和。
// 区间状态更新函数
void update_state(int pos, int delta) {
freq_count[arr[pos]] += delta;
if (freq_count[arr[pos]] == 1) {
result++;
} else {
int old_val = freq_count[arr[pos]] - delta;
result += freq_count[arr[pos]] * freq_count[arr[pos]] - old_val * old_val;
}
}
// 查询处理逻辑
while (left < query[i].start) update_state(left++, -1);
while (left > query[i].start) update_state(--left, 1);
while (right < query[i].end) update_state(++right, 1);
while (right > query[i].end) update_state(right--, -1);
优化策略
奇偶优化技巧
为了避免右指针频繁往返移动，可采用以下策略：
- 奇数区块：左端点升序排列
- 偶数区块：左端点降序排列
这种交替排序方式能显著减少指针移动距离，通常可提升约 30% 性能。
高级变体
支持修改的莫队
在基础版本基础上增加时间维度，同时维护三种指针：左边界、右边界和时间戳。
// 时间维度处理
while (timestamp < modification[i].time) {
timestamp++;
if (mod_records[timestamp].pos >= left && mod_records[timestamp].pos <= right) {
update_state(mod_records[timestamp].pos, 1);
update_state(original_value[mod_records[timestamp].pos], -1);
}
swap(current_array[mod_records[timestamp].pos], mod_records[timestamp].new_val);
}
while (timestamp > modification[i].time) {
// 类似处理...
}
二维扩展
将一维区间扩展至二维矩形区域，需要维护四个边界指针。
// 边界扩展操作示例
while (top_row < target.top) {
for (int col = left_col; col <= right_col; col++)
update_cell(top_row, col, -1);
top_row++;
}
while (left_col > target.left) {
left_col--;
for (int row = top_row; row <= bottom_row; row++)
update_cell(row, left_col, 1);
}
// 其余边界类似处理...
回滚型莫队
当删除操作难以实现时，采用只增不减的策略，并通过状态回滚保证正确性。
if (same_block(query[i])) {
// 同区块暴力处理
} else {
if (new_block(query[i])) {
// 清理历史状态并重置指针
}
// 右指针扩展
while (right_ptr < query[i].right) process_right(++right_ptr);
// 左指针临时扩展
int temp_left = left_ptr;
while (temp_left > query[i].left) process_left(--temp_left);
// 回滚左指针状态
rollback_left(temp_left, left_ptr);
}
树上应用
通过欧拉序将树结构转化为线性序列，从而应用莫队算法。
// 树遍历生成序列
void dfs(int node) {
euler_sequence.push_back(node);
for (auto child : tree[node]) dfs(child);
euler_sequence.push_back(-node); // 离开标记
}
// 状态转换规则
// 正数: 添加节点
// 负数: 移除对应正数节点
