Mo's algorithm

Mo’s algorithm について説明します。

Mo’s algorithm の動作の様子をアニメーションにしてみました。アニメーションを見れば、計算量解析パートは自明でしょう。IE以外なら見れると思います。 https://pekempey.github.io/mo_algorithm/mo.html

Mo’s algorithm とは

区間クエリ系の問題を解くためのアルゴリズム。次のようなクエリに対して有効。

  • 要素が更新されない
  • クエリの先読みが可能
  • 区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる

Mo’s algorithm の流れ

まず区間を平方分割し、左端をキーにしてクエリをバケットに入れる。その後、各バケット内で右端をキーにしてソートする。

結局のところ上の操作は次の比較関数でソートすることと同じ。

def compare (a, b):
    S = sqrt(N)
    if a.L / S != b.L / S:
        return a.L < b.L
    return a.R < b.R

前処理はこれで終わり。ここからどのようにクエリを処理するのか。

実はしゃくとりっぽく区間の伸ばしたり縮めたりして、現在のクエリ区間から次のクエリ区間まで変化させるだけで良い。

要するに次のような処理を行う。

queries を上述の compare でソート

i, j = 0, -1
for l, r, index in queries:
  while i > l: add(--i)     # [i, j] -> [i-1, j]
  while j < r: add(++j)     # [i, j] -> [i, j+1]  
  while i < l: remove(i++)  # [i, j] -> [i+1, j]
  while j > r: remove(j--)  # [i, j] -> [i, j-1]
  ans[index] = answer

これだけで計算量が O((N+Q)√N) になる。

Mo’s algorithm の計算量

左端 i と右端 j の振る舞いに着目する。

左端 i の振る舞い

基本的にはバケット内で移動するが、O(√N) 回バケットをまたいだ移動をする。

f:id:pekempey:20160123152707p:plain:w400

バケット内で移動する場合、一回のクエリあたり距離 O(√N) の移動するのでクエリ全体では O(Q√N)。 バケットをまたいだ移動は全体で O(N)。 したがって総移動回数は O(Q√N + N) 回。

右端 j の振る舞い

左端が同じバケットにある限りひたすら右に移動し、 左端のバケットが切り替わるタイミングで距離 O(N) の移動を行う。

f:id:pekempey:20160123153929p:plain:w400

したがって総移動回数は O(N√N) 回。


以上より O((N+Q)√N) であることが分かる。

参考文献

更新履歴

  • (2017/8/6) D-query についての説明を全て削除しました。