コンテンツにスキップ

セグメント木のリンク集

セグメント木について、参考になる記事や資料をまとめました。

セグメント木は、列に対して「1 点の更新」と「区間の積(和・最小値・最大値など)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。演算が結合法則を満たし、単位元を持つ(モノイドである)ことが条件です。区間に対する更新も行えるように拡張したものを、遅延評価セグメント木(遅延セグ木)と呼びます。区間 chmin のように遅延セグ木にそのままでは載らない作用を扱うための拡張に、Segment Tree Beats があります。

セグメント木そのものを解説する講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 区間の情報をどう持ち、どう結合するかを、区間和・区間最小値から関数合成・行列まで例を挙げて解説しています。セグメント木を使ったことがある人向けです。
  • 代数構造用語集
    • モノイドなどの用語の定義です。
  • 永続セグメント木
    • 過去の状態を残したまま更新できるようにしたセグメント木です。
  • セグメント木(Wikipedia)
    • 前半は Bentley による元々の segment tree(線分の集合を格納し、ある点を含む線分を列挙する木)の説明で、競プロで使うものとは別物です。モノイドへの一般化と配列による実装は後半にありますが、細かい誤りがあるので、ほかの資料と合わせて読むのがおすすめです。
  • Segment Tree(cp-algorithms)
    • 英語の定番の解説です。応用例が多く載っています。