長さNの静的な値の列が与えられた時に、前処理O(NlogN)で、その列の上の区間に対する演算がO(1)で計算できるようになるデータ構造
使える演算は具体的にはminなど、argminもOK
<ul>
<li><a href="/ja/%E4%BA%A4%E5%8F%89%E5%8D%8A%E6%9D%9F">交叉半束</a><ul>
<li><a href="/ja/%E7%B5%90%E5%90%88%E6%B3%95%E5%89%87">結合法則</a>: $(a * b) * c = a * (b * c)$</li>
<li><a href="/ja/%E4%BA%A4%E6%8F%9B%E6%B3%95%E5%89%87">交換法則</a>: $a * b = b * a$</li>
<li><a href="/ja/%E5%86%AA%E7%AD%89%E6%80%A7">冪等性</a>: $a * a = a$</li>
</ul>
</li>
</ul>
構築O(N log N)
<ul>
<li>各点から2ベキの長さの区間のminを計算</li>
<li>2^kの長さの区間は半分の長さの区間2つから定数オーダーで計算可能なので小さい方からDPする</li>
</ul>
クエリー
<ul>
<li>クエリー区間の長さより小さい最大の長さの計算済み区間を2つ使ってクエリ区間を覆う</li>
<li>例えば1〜7の区間に対して1〜4と4〜7で覆う</li>
<li>クエリ区間の最小値は2つのどちらかの区間での最小値</li>
</ul>
列が更新される時は<a href="/ja/%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8">セグメント木</a>を使う
<ul>
<li><a href="/ja/%E3%82%B9%E3%83%91%E3%83%BC%E3%82%B9%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%E3%81%A8%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8">スパーステーブルとセグメント木</a></li>
</ul>
木の<a href="/ja/%E6%9C%80%E5%B0%8F%E5%85%B1%E9%80%9A%E7%A5%96%E5%85%88">最小共通祖先</a>を<a href="/ja/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%83%84%E3%82%A2%E3%83%BC">オイラーツアー</a>+<a href="/ja/Range%20Minimum%20Query">Range Minimum Query</a>で求める場合に。
<ul>
<li><a href="https://ikatakos.com/pot/programming_algorithm/graph_theory/lowest_common_ancestor">最小共通祖先 [いかたこのたこつぼ]</a></li>
</ul>
<a href="https://ei1333.github.io/luzhiled/snippets/structure/sparse-table.html">スパーステーブル(Sparse-Table) | Luzhiled’s memo</a>
2次元に拡張できる
<ul>
<li><a href="https://www.hamayanhamayan.com/entry/2018/01/03/035508">競技プログラミングにおけるSparse Table問題まとめ - はまやんはまやんはまやん</a></li>
<li><a href="/ja/2D%20Sparse%20Table">2D Sparse Table</a><ul>
<li><a href="/ja/2D%20Range%20Minimum%20Query">2D Range Minimum Query</a><ul>
<li><a href="http://codeforces.com/blog/entry/45485">2D Range Minimum Query in O(1) - Codeforces</a></li>
</ul>
</li>
</ul>
</li>
</ul>
<a href="/ja/%E3%82%B9%E3%83%91%E3%83%BC%E3%82%B9%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB">スパーステーブル</a>