構築 O(N) クエリ O(1) の RMQ

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 とかでガチャガチャやると行ける！みたいな感じです。詳しくは (特に後半部分) 以下の記事が素晴らしいのでそちらを参照してください。

qiita.com

　こちらの記事で割愛されているスタックの使い方について説明します。小ブロック内の要素を前から見ていき、スライド最小値のように、単調増加する列をインデックスで保持しておきます。B[i] と B[スタックの top] を比較し、スタックが空になるか B[スタックの top] が B[i] より小さくなるまでスタックから pop します。するとそのときのスタックの top が g[i] となります(空の場合は -1)。g[i] を求めたら i をスタックに push します。スタックは各インデックスが1回づつ push されるので、このアルゴリズムは線形です。