莫队算法学习笔记

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

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

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

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

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