Sparse Table

長さNの静的な値の列が与えられた時に、前処理O(NlogN)で、その列の上の区間に対する演算がO(1)で計算できるようになるデータ構造

使える演算は具体的にはminなど、argminもOK

結合法則: $ (a * b) * c = a * (b * c)

交換法則: $ a * b = b * a

冪等性: $ a * a = a

構築O(N log N)

各点から2ベキの長さの区間のminを計算

2^kの長さの区間は半分の長さの区間2つから定数オーダーで計算可能なので小さい方からDPする

クエリー

クエリー区間の長さより小さい最大の長さの計算済み区間を2つ使ってクエリ区間を覆う

例えば1〜7の区間に対して1〜4と4〜7で覆う

クエリ区間の最小値は2つのどちらかの区間での最小値

列が更新される時はセグメント木を使う

2次元に拡張できる