2019/03/10 大雑把な説明を追加しました
2019/07/08 細微な修正を行いました
概要
RMQ は競プロでも頻出のデータ構造です。本記事では競プロで実際に速度の向上が見込める高速な RMQ の実装について書きます。
本題
一般に良く知られる LCA に変換して ±RMQ にする方法は定数倍が懸念されたため、本記事では直接解く方法で実装しました。
基本戦術は SparseTable です。これは構築が Ο(NlogN)、クエリが Ο(1) のデータ構造でした。そこで logN 個程度の要素をひとつのブロックにして、得られたブロックの列について SparseTable を構築すれば、要素数が Ο(N/logN) となって構築時間が Ο(N/logN*log(N/logN)) ≦ Ο(N) になる、という算段です。
するとブロックの内部の RMQ が定数時間でできないといけないわけですが、ブロックサイズは logN → 整数型に入る → 良い感じに減少列を bit で管理してビットマスクと ctz とかでガチャガチャやると行ける！みたいな感じです。詳しくは (特に後半部分) 以下の記事が素晴らしいのでそちらを参照してください。
こちらの記事で割愛されているスタックの使い方について説明します。小ブロック内の要素を前から見ていき、スライド最小値のように、単調増加する列をインデックスで保持しておきます。B[i] と B[スタックの top] を比較し、スタックが空になるか B[スタックの top] が B[i] より小さくなるまでスタックから pop します。するとそのときのスタックの top が g[i] となります(空の場合は -1)。g[i] を求めたら i を スタックに push します。スタックは各インデックスが1回づつ push されるので、このアルゴリズムは線形です。
実装
msb() を定数時間と仮定するのは甘えでは？と感じる方もいらっしゃるかもしれません。解決方法は主に2つあります。
1. かなり複雑なbit演算をする
乗算を巧みに使った演算でワード長の整数の msb() は定数時間になりますが、定数倍が大きく、期待は難しいです。
2. テーブルを作る
ブロックサイズは logN より小さくできますので、余裕をもってテーブルを計算することが出来ます。試してみた限りだと、組み込みの関数などと大きな差が出ることはないようです。
AOJ DSL_3_D を解く
3種類の方法で解き、速度の比較をしました。実行時間はややばらつくため完全ではないので、参考程度にしてください。
1. Segment Tree
AIZU ONLINE JUDGE: Code Review
2. Sparse Table (分割統治無し)
AIZU ONLINE JUDGE: Code Review
3. 本記事のRMQ
