問題概要
問題文 → ■
列が静的（Static）というのは，変更されないということです．静的な列に対する区間 $\min$ クエリに答える問題です．
この記事の読者であればこの問題を簡単に解ける人がほとんどだと思いますが，手法によっては知らないものがあるかもしれないので，興味があれば確認してみてください．
以下で述べる解法の多くは，$\min, \max$ 操作に限らず任意のモノイドに適用できます．学術的な文献は，モノイドよりも半群（semi-group）の方が検索ワードとして良さそうでした．
日本語記事では次が非常によくまとまっていると思います．本記事との重複も多いです．
本記事では，ワードサイズの整数の最下位・最上位のビットの取得が $O(1)$ 時間でできる計算量モデルを仮定しています（あるいは $N$ 以下の整数に対する適当な lookup table を事前計算することでこれらを $O(1)$ 時間で取得できるようにしてもよいです）．
ところどころ提出の実行時間を書いていますが，全く同じコードを連投しても実行時間が 20 ms 近く上下してしまうことがあるので，より詳しく実行時間を比べたい場合には Library Checker への提出以外の手段をとった方が良いかもしれません（こういうのどうすればいいんだろうなあ）．
解法
セグメント木
セグメント木の解説は世の中にたくさんあると思うので，省略します．私も解説したことがあります．
計算量は，構築 $\Theta(N)$，クエリあたり $\Theta(\log N)$ です．なるべく本問題に必要なところだけを実装した例を挙げておきます．
- 解答例（84ms）
本問題は整数の min という演算ですが，これを任意のモノイドに一般化できて，セグメント木はモノイドの区間積が扱えるというのが現在の主流な理解のひとつです．実装もこの一般化が扱えるようにしておくと便利です．モノイドのような代数系を扱うという形に抽象化したデータ構造の実装には，noshi91さんの記事 で解説されているようにいくつかの方法が知られており，私の実装ではこの記事の E を用いています．赤コーダー以上でもこの辺の設計は人によって結構ばらけているので，好みの実装を探してみてください．最近では Atcoder Library の実装方針を参考にしている人も多いと思います．
セグメント木では，点更新を行うこともできます．そのようなメソッドの verify には Point Set Range Composite を使うと良いでしょう．
分割統治の利用
使用頻度は後述の DST に劣ると思いますが，理解の順序としては DST の理解の助けとなると思うので先にこちらを扱います．
解法は，私が この記事 で私が解説しました．時間計算量は $\Theta(N\log N+Q)$，空間計算量は $\Theta(N+Q)$ です．
解答例1は，私が記事で解説したものほとんどそのものです．解答例2はこれを洗練させて高速化しています．区間 $[0,2^n)$ に対して通常の分割統治を実行した場合，区間 $[a,b)$ に対して $L\leq a < M< b \leq R$ となる $(L,M,R)$ がどのようなものであるかを考えると，この $L, M, R$ は適当なビット演算で計算できます（$a, b-1$ 番目の要素が $M$ をまたぐところなので，$a \mathrm{XOR} (b-1)$ の topbit を見るというタイプの計算をすればよいです）．そこで予めクエリを振り分けておき，再帰関数そのものは呼ばずにクエリ処理しています．また，ランダムケースはかなり高速な割に，「small_width_query」のケースで実行が遅いため，区間長が短い場合には愚直解に取り換えるというようなチューニングを行いました．
本解法はクエリがオフラインであるという前提でしか使えないという欠点があります．また $N=Q$ に近い場合にはセグメント木が十分パフォーマンスが良いことが多いため，それほど使用頻度は高くないと思います．一方本解法が計算量で上回る設定もあるということなども私の記事で解説しています．
Disjoint Sparse Table （DST）
Disjoint Sparse Table は，上述の分割統治の解法をそのままオンラインクエリに対応できるようにしたデータ構造です．各 $k$ に対して再帰の $k$ 回目に $i\in [L,R)$ となる区間を訪れるときの $[i, M)$ や $[M, i]$ の累積積を $k$ 個目のテーブルに持ちます．もとの列の長さが $2$ のべき乗であるように考えて分割統治の分割位置を選べば，上述のようにクエリ区間に対する計算がどこに保持されているかを適当な bit 演算で取得できるようになります．
- 解答例（64ms）
この解法の時間計算量は $\Theta(N\log N+Q)$，空間計算量は $\Theta(N\log N)$ です．分割統治解法と比べると，オンラインクエリに対応した代わりに空間計算量が大きくなります．
$N=Q$ に近い場合，セグメント木と比べると，時間計算量オーダーが変わらず，一方で空間計算量が増える，列が静的なものに限定されてしまうなどのデメリットもあるため，DST よりもセグメント木を使っていればよいということが多いです．逆に言うと DST を使うべきは，$Q$ が $N$ に比べてかなり大きい場合と考えるとよいでしょう．
見た目上は $N$ と $Q$ が近くても，他のデータ構造の内部でモノイド積の計算が必要となる場合には DST を用いることで計算量が改善される場合があります．例えば次のような場面で TLE との戦いで利用したことがあります．
- $N$ 頂点の木に静的なデータがあって $Q$ 回のパスクエリを HLD で処理する場合
- セグメント木を使うと空間 $\Theta(N)$，時間 $\Theta(N+Q\log^2 N)$．
- DST を使うと空間 $\Theta(N\Theta(N))$，時間 $\Theta(N\log N+Q\log N)$．
- $H\times W$ の密な 2 次元配列に静的なデータがあって $Q$ 回の矩形クエリを処理する場合
- 2 次元セグメント木を使うと空間 $\Theta(HW)$，時間 $\Theta(HW+Q\log H\log W)$．
- 1 次元目をセグメント木，2 次元目を DST にすると，空間 $\Theta(HW\log W)$，時間 $\Theta(HW+Q\log H)$．
Sparse Table
Sparse Table も DST と同様に，列が静的であるという制約のもとで，$\Theta(N\log N)$ 時間の前計算により $\Theta(1)$ 時間でのクエリ処理を実現するものです．ただし，モノイドに冪等性が必要になります（可換性は不要）．
仕組みは DST とはまあまあ違って，こちらはダブリングと呼ばれるテクニックにアイデアが近いです．実装が DST よりも少し簡単だと思います．
- 解答例（59ms）
DST と比べた性能の違いはあまりなくて，時間・計算空間量もオーダーは同じです．DST と比べたメリットはわずかに高速なこと，デメリットはモノイドに冪等性が必要なことです．速度差の違いは大きくはないので所持しておくべき優先度は DST よりも低いと個人的には考えています．
使用する場面の考え方は DST と同様で，モノイドが冪等だったら DST の代わりに使う感じだと思います．対象となるモノイドは私の経験上，ほとんど max, min です．これに max をとるインデックスも持たせる等の変種もあります．例えば，LCA や，suffix の LCP の計算を非常に多くの回数計算する際に用いるというのが代表的な用途だと思います．
他に冪等なモノイドとしては，bitwise and, or や $\gcd, \mathrm{lcm}$ があります．
Sqrt Tree
DST は，$\Theta(N\log N)$ 時間の空間・事前計算を利用し，クエリは $1$ 回のモノイド積によって答を求めることができました．Sqrt Tree はクエリの際に $2$ 回のモノイド積を要求する代わりに空間・事前計算を $\Theta(N\log \log N)$ 時間に抑えたものです．
なお上の解答例では，非常に短い区間に対するクエリ（ある $n$ に対して $8n\leq l < r \leq 8n+8$ を満たすクエリ）に対しては愚直なループを使っているため，$2$ 回以上のモノイド積を要求していることもあります．
列全体を長さ $B$ のブロック $N/B$ 個に分割します．次の $3$ 種のデータを持ちます．
- (1) 各要素に対して，ブロック内でその要素までの prefix product．
- (2) 各要素に対して，ブロック内でその要素以降の suffix product．
- (3) あるブロックの左端からあるブロックの右端までの product．
(1), (2) は空間・時間 $\Theta(N)$ で計算できます．(3) は空間・時間 $\Theta((N/B)^2)$ で計算できます．
この $3$ 種のデータを利用すると，クエリ区間があるブロックに含まれる場合を除いてクエリに答えられるようになります．ブロックから左右にはみ出している部分とその内側という分割をすればよいです．課題はクエリ区間があるブロックに含まれる場合ということになるため，このようなデータ構造を今度は各ブロック内に再帰的に作って処理します．
$B=\sqrt{N}$ 程度にとると再帰の段階が $\Theta(\log\log N)$ 段階で終了し，各段階で $\Theta(N)$ の前計算を行うため，冒頭に述べた計算量となります．
DST と比べるとクエリ処理についてはモノイド演算の回数が $1$ 回から $2$ 回へと悪化しています．使用すべき状況は，セグメント木ではクエリの遅さが気になり，DST では構築の遅さ（あるいはメモリ）が気になる場合ということになるでしょう．個人的には使用経験がないので役に立つ典型的な状況が分からないです．疎な 2 次元セグメント木や wavelet matrix に静的なモノイド列を持たせる際などに使うと $\log^2$ の類回避できていて良いかもしれません．区間に辺を張るテクニックにおいてセグメント木の代わりに使うというのも面白い気がします（MLE が気になりやすい場面なので）．
Library Checker 最速提出について
2024/02/05 現在の最速提出はおそらく 2023/11/6 時点の私の最速提出をもとに実装しており，同じ解法です．私の提出はこの提出（chaihf さん）をもとにしましたが，同様の解法はそれ以前にも提出されているようです．この方法を解説します．
- 解答例（29ms）
この解法では，区間クエリに $3$ 回のモノイド演算で答えることを目指して前計算を行います．列全体を長さ $B$ のブロック $N/B$ 個に分割し，次の $3$ 種のデータを計算します．
- (1) 各要素に対して，ブロック内でその要素までの prefix product．
- (2) 各要素に対して，ブロック内でその要素以降の suffix product．
- (3) あるブロックの左端からあるブロックの右端までの product を計算するための DST (Sparse Table)．
Sqrt Tree のときとの違いは (3) のみで，Sqrt Tree ではこの部分を $\Theta((N/B)^2)$ 時間の事前計算，クエリには $0$ 回のモノイド演算で処理していました．この部分で DST を使って $1$ 回のモノイド演算に置き換える代わりに，必要な事前計算を減らしています．
以上で，$\Theta(N+(N/B)\log(N/B))$ の事前計算によって，クエリ区間があるブロックに完全に含まれる場合を除き，$3$ 回のモノイド演算でクエリに答えられるようになります．
クエリ区間がひとつのブロックに完全に含まれているクエリ区間に対しては，愚直なループで答を計算してしまいましょう．ブロックごとのデータ構造は持たなくてよいので実装もかなり簡単です．上述の提出では $B=16$ としており，最悪ケースでは $15$ 回程度のモノイド演算を行っています．
なお，クエリ区間がブロックに含まれる場合の処理について，Sqrt Tree のときと同様に再帰的に同じ構造を構築することが考えられます．$B=\log N$ としてこの方法をとった場合，理論上の事前計算の計算量オーダーは，$\Theta(N\log^{*}N)$ ということになります．
参考：事前計算 $\Theta(N)$ クエリ $\Theta(\alpha(N))$
同様のアイデアで，このような計算量が達成できます．クエリあたり $k$ 回のモノイド演算を達成するには，ブロックに分割し，ブロック内での prefix, suffix および，ブロック全体からなる列に対して $k-2$ 回のモノイド演算で区間クエリできるデータ構造を持ちます（そのようなデータ構造を $k$ に対して再帰的に定義します）．ブロック内に完全に収まる区間に対しては再帰的に処理します．ここで $N$ に対して $k$ を最適にとることを考えると，$\alpha(N)$ が発生するという要領です．そのままだと空間 $\Theta(N\alpha(N))$ になりますが，少し工夫すれば空間 $\Theta(N)$ になります．
実装例は省略します．というか，上で解説してきた手法がこれらの $k$ が小さな特殊ケースと見なすこともできて，ある意味では既にこれまでで実装例を紹介したとも言えます．
線形 RMQ
事前計算・空間が $\Theta(N)$ でクエリ $\Theta(1)$ になります．なお一般の半群という状況では計算量の下界の評価もされていてこの計算量は達成不可能だと分かっているので，min, max に特化した手法ということになります．
まず，大きさ $B=\log N$ のブロックに分割して Sparse Table を利用すれば，クエリ区間があるブロックに完全におさまる場合以外は $3$ 回のモノイド演算で答が出るようになるのでした．あとは，クエリ区間の長さが $B$ 以下ある場合に対応すればよいです．
私の実装では $i$ を降順にループしながら，$j\in [i, i+B)$ かつ $[i,i+j]$ での最小値が $i+j$ でとるような $j$ 全体をビット列で持っています．スタックによるスライド最小値を理解していれば，実装は簡単だと思います．
なお，モノイドを特殊化して計算量オーダーを落としたものの，リジャッジを試みても，Library Checker 最速より少し遅い実行時間しか達成できていません．ちょっと用途が想定できないな…．
コメント
個人的に Sqrt Tree や線形 RMQ は実装したことがなかったので勉強になりました．競技プログラミングではあまり有名知識ではないですが，インタラクティブ問題などでは問いやすそうな発想な気がします．
各解法がどのような場面で使えるかについての考察も少し書いてみましたが，どうだったでしょうか．制約によって手法の優劣が変わるところも多くなかなか比較が難しいです．
