はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるSparse Table問題まとめ

Sparse Table

  • 普通のSparse Table
    • 結合則と冪等性が成り立つ操作ならば構築O(NlogN),クエリO(1)でできるデータ構造
      • 結合則: 順序逆にしても結果が同じ
      • 冪等性: 1回やっても複数回やっても結果が同じになる(maxとかはそう)
    • セグメントツリーとは異なり更新はできない
    • 解説
  • Disjoint Sparse Table
    • 結合則が成り立つ操作ならば構築O(NlogN),クエリO(1)でできるデータ構造
    • 解説
  • 2DにRMQを拡張すると構築O(NMlogNlogM),クエリO(1)でできる 出典