セグメント木のリンク集
セグメント木について、参考になる記事や資料をまとめました。
セグメント木は、列に対して「1 点の更新」と「区間の積(和・最小値・最大値など)の取得」をどちらも で行えるデータ構造です。演算が結合法則を満たし、単位元を持つ(モノイドである)ことが条件です。区間に対する更新も行えるように拡張したものを、遅延評価セグメント木(遅延セグ木)と呼びます。区間 chmin のように遅延セグ木にそのままでは載らない作用を扱うための拡張に、Segment Tree Beats があります。
まず読むもの
Section titled “まず読むもの”- セグメント木を徹底解説!0から遅延評価やモノイドまで(アルゴリズムロジック)
- 基本から遅延評価、モノイドまでを 1 本で扱う入門記事です。
- セグメント木をソラで書きたいあなたに・遅延評価セグメント木をソラで書きたいあなたに(hogecoder)
- 区間最小と、区間加算・区間和を題材に、自分で実装できるようになることを目標にした解説です。
AtCoder Library(ACL)
Section titled “AtCoder Library(ACL)”- segtree のドキュメント・lazysegtree のドキュメント
- 公式の仕様です。セグメント木上の二分探索
max_right・min_leftの仕様もここにあります。
- 公式の仕様です。セグメント木上の二分探索
- AtCoder LibraryのLazy Segtreeの使い方・AtCoder LibraryのLazy Segtreeのチートシート(ARMERIA)
- ACL の遅延セグ木に渡す関数の決め方の解説と、よく使う 6 パターン(区間加算・区間変更 × 最小値・最大値・和)のコード集です。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”セグメント木そのものを解説する講座はまだありませんが、関連する講座があります。
- 区間クエリのためのモノイド設計
- 区間の情報をどう持ち、どう結合するかを、区間和・区間最小値から関数合成・行列まで例を挙げて解説しています。セグメント木を使ったことがある人向けです。
- 代数構造用語集
- モノイドなどの用語の定義です。
- 永続セグメント木
- 過去の状態を残したまま更新できるようにしたセグメント木です。
実装を詳しく知りたいとき
Section titled “実装を詳しく知りたいとき”- Segment Tree のお勉強(1)・Segment Tree のお勉強(2)(maspyのHP)
- 非再帰(ボトムアップ)の実装を図で解説しています。(1) が通常のセグメント木、(2) が遅延評価セグメント木です。
- Segment Tree (セグメント木)(Luzhiled’s Library)
- ライブラリとそのドキュメントです。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- セグメント木(Wikipedia)
- 前半は Bentley による元々の segment tree(線分の集合を格納し、ある点を含む線分を列挙する木)の説明で、競プロで使うものとは別物です。モノイドへの一般化と配列による実装は後半にありますが、細かい誤りがあるので、ほかの資料と合わせて読むのがおすすめです。
- Segment Tree(cp-algorithms)
- 英語の定番の解説です。応用例が多く載っています。
- AtCoder Library Practice Contest J - Segment Tree
- AtCoder Library Practice Contest K - Range Affine Range Sum
- AAL Contest 001: Let’s use segtree!
- Library Checker:Point Add Range Sum(BIT でも解けます)、Point Set Range Composite、Range Affine Range Sum
このブログの記事
Section titled “このブログの記事”- ABC478 F - Min-First Search
- 区間最大値のセグメント木で
min_leftを使い、二分探索しています。
- 区間最大値のセグメント木で
- SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
- 座標圧縮した累積和の個数を、区間和のセグメント木で数えています。