Disjoint Sparse Table

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

演算に要求される条件

• 結合則: $(a\ast b)\ast c=a\ast (b\ast c)$
• 単位元や逆元は必要ない

加算のような逆元のある演算についてはこれを使う必要はない

• 累積和を使って構築O(N)で同じことができるから

逆元のない乗算などで左右から累積積で一つ除き積を実現できる

• これをたくさんの累積積を組み合わせて任意の区間の積を計算できるようにしたのがDisjoint Sparse Table

Disjoint Sparse Table と セグ木に関するポエム - noshi91のメモ

Sparse Table