莫队算法学习笔记

算法竞赛中有这样一类题目,给定一个序列 ,每次查询 区间的信息。这类题目没有修改操作,只有查询,并且操作没有加密(允许离线),莫队算法就是针对这类题目的一个离线算法。

莫队算法的核心思想是,假如我们已经知道了 的答案,又可以很方便地向 扩展,就可以实现让答案在每个询问之间转移。假设每次扩展的时间为 ,又因为每次转移最多有 次扩展,所以算法总时间复杂度为 ,通常会超时。

我们可以将区间分为 块,每块的大小为 ,并且将询问以左端点所在的块为第一关键字、以右端点为第二关键字排序,之后再进行上述算法。

排序后,只有第一关键字不同的询问之间才会产生块之间的转移,而又因为共有 块,所以不同块之间的转移最多发生 次,不同块之间转移的总次数为 。每一块的大小为 ,即每一块内最多有 个不同的区间。所以,每经过一个块,都要进行 次转移,乘上总块数 ,即相同块内的转移的总次数为

每次扩展的时间复杂度不同时,适当调整块的大小,可以降低使整个算法的时间复杂度。