Mo's algorithm(クエリ平方分割)の話

Mo's algorithmの紹介記事です。

Mo's algorithmとは

区間に対するクエリを高速に処理するためのアルゴリズムです。
次のような問題を考えてみましょう。

長さ $N$ の数列 $A$ がある。$l_i,r_i$ に関するクエリがたくさん飛んでくるので、$[l_i,r_i)$ の最小値を答えよ。

これは、みなさんよくご存じ、Segment TreeやSparse Tableを使うことで高速に処理できます。
では、次の問題はどうでしょう。

長さ $N$ の数列 $A$ がある。$l_i,r_i$ に関するクエリがたくさん飛んでくるので、$[l_i,r_i)$ の値の種類数をオフラインで答えよ。

これを同じようにSegment TreeやSparse Tableで解くことはできません。
必要となる区間のマージに $O(N)$ かかってしまうからです。
では、これを高速に解く方法はないでしょうか。実は、この問題は、クエリがオフラインならMo's algorithmと呼ばれるアルゴリズムを使って、高速に解くことができます。

Mo's algorithmの仕組み

Mo's algorithmは、クエリを先読みして適切な順番に並び替えることにより、計算量を減らすテクニックです。
まず、区間全体を $\sqrt N$ 個ずつまとめ、平方分割をします。
ここで、与えられたクエリを、次のようにソートします。

• 平方分割後、どこの区間に含まれるかの順序でソートする。
• 含まれる区間が同じ場合は、右端の順でソートする。

こうしてソートした順序で、前の結果を利用しながらクエリを処理していきます。具体的には、左右の端を伸ばしたり縮めたりすることで、前の結果をもとに計算します。
計算量を解析してみましょう。
左端は、区間ごとにソートされていることにより最大 $\sqrt N$ ずつしか動きません。
また、右端は、左端がひとつの分割された区間に属している間は、右端でのソート順によって合計で最大 $N$ しか動きません。
よって、左端の移動では $O(Q\sqrt N)$, 右端は $O(N\sqrt N)$ となります。
これで、合計の計算量が $O((N+Q)\sqrt N)$ になります。
ただし、左右の端を動かすのにSegment Treeなどを使ったりすれば、当然全体に $\log$ がつくので、$O((N+Q)\sqrt N\log N)$ などになることもあります。

名前の由来

Mo's algorithmの名前の由来について紹介します。
Mo's algorithmは、2009年の中国における情報オリンピック春合宿で出題された問題、小Z的袜子(hose)で初めて使われたようです。
ところで、イギリス英語で靴下をhoseと言うようですね。初めて知りました。
問題概要の訳を示します。

$N$ 枚の靴下が並んでいて、それぞれに色がある。区間が $M$ 個与えられるので、ランダムに $2$ 枚の靴下を区間から選んだとき、同じ色である確率を求めよ。
制約:$N,M\leq 50000$

まさにMo's algorithmで解ける問題ですね。
区間の遷移の際には、Segment Treeを用いて色ごとにその色の靴下を2枚選べる通り数を管理し、クエリに答える際には区間和を用いて、全体の通り数に占める確率を計算すればよいです。
なお、オリジナルの問題では有理数の形での出力が求められるようで、少し特殊だな、と思いました。
これに対して、莫涛(Mo Tao)氏が発明したアルゴリズムがMo's algorithmというわけです。

実装例

実装は非常に簡単です。
分割する区間ひとつひとつのサイズを決定した後、次のような関数を用いてクエリをソートすればよいです。

int M;  //分割するひとつひとつの区間サイズ
bool func(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    if (lhs.first / M < rhs.first / M)return true;
    if (lhs.first / M == rhs.first / M && lhs.second < rhs.second)return true;
    return false;
}

これで、区間の左端と右端を次のクエリの左右の端に向けてずらしていけばよいです。

問題例

先ほど挙げた中国の情報オリンピックの問題の他に、日本語ではJOI2014春合宿Day1-3 歴史の研究(Historical Research)がMo's algorithmで解けます。定数倍が少し重いですが、高速化をすると通ります。想定解法はバケット法のようです。
提出コード

おわりに

そこまで頻出のアルゴリズムではないですが、これがないと解けない問題も存在します。覚えておきましょう。