Segment Tree Beats のリンク集
Segment Tree Beats について、参考になる記事や資料をまとめました。
Segment Tree Beats(Segment Tree Beats!、中国では「吉老师线段树」とも)は、2016 年ごろに吉如一(jiry_2)が中国の国家集訓隊論文で発表した、遅延評価セグメント木の拡張です。区間 chmin()のように、遅延セグ木にそのままでは載らない作用を扱えます。名前はアニメ「Angel Beats!」に由来します。
考え方は「ノードへの作用が計算できないときは、子に再帰して計算し直す」というものです。区間 chmin と区間和の場合、各ノードに最大値・厳密に 2 番目に大きい値・最大値の個数・和を持ちます。 が最大値以上なら何もせず、2 番目の値より大きければ最大値だけが に変わるので和もすぐ更新でき、それ以外のときだけ子に再帰します。再帰が起きる回数をポテンシャルで抑えるのがこの手法の要で、問題ごとに作用の設計と計算量の解析が必要です。
計算量は次のとおりです。
- 区間 chmin・chmax と区間和だけなら、全体で償却 です。
- 区間加算も混ぜると です。 のままではないかという予想もありましたが、2025 年に になる入力が見つかり、 と分かりました。古い資料では「もしかしたら かも」と書かれていることがあります。
まず読むもの
Section titled “まず読むもの”- Segment Tree Beatsの実装メモ (基本まわり)(日々drdrする人のメモ)
- 区間 chmin と区間最大値・区間和(HDU 5306 Gorgeous Sequence)、区間 chmin・chmax の場合を、図つきで実装の流れに沿って説明しています。ノードに何を持ち、どの条件で再帰を打ち切るかが分かります。最後に区間加算・区間代入を混ぜる場合にも少し触れています。計算量の解析は含みません。コードは C++ です。
- コードの区間最大値は範囲外で を返すので、負の値がある問題ではそのままでは使えません。
- ABC256 Ex - I like Query Problem の解説(Nyaan、AtCoder 公式解説)
- 区間を にする操作を含む問題で、解法 2 として Segment Tree Beats を説明しています。ACL の
lazy_segtreeの実装を土台に、作用が「失敗」したら子に再帰するように拡張する、という説明で、遅延セグ木を書ける人には一番入りやすい資料です。各ノードに「区間の値がすべて等しいか」のフラグを持ち、値が半分以下になることを使ったポテンシャルで を示しています。
- 区間を にする操作を含む問題で、解法 2 として Segment Tree Beats を説明しています。ACL の
ACL の lazy_segtree から作る
Section titled “ACL の lazy_segtree から作る”- atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats(ひとなので)
- ACL の
lazy_segtreeのall_applyにif (d[k].fail) push(k), update(k);を書き足し、ノードに失敗フラグを持たせることで、汎用の Segment Tree Beats にする方法です。例題として yukicoder No.880(区間代入・区間 gcd)、CS Academy の And or Max(区間 and・or)、Library Checker の Range Chmin Chmax Add Range Sum のノードの設計があります。Beats の存在は知っているが実装したことはない人向けで、導入の解説はありません。 - 注 4 の「composition 関数は lazy_segtree 内の二か所でしか呼ばれません」は、
mapping関数の誤りです。Library Checker の参考提出へのリンク(old.yosupo.jp)は切れています。
- ACL の
- ABC430 G - Range Set Modifying Query の解説(kyopro_friends、AtCoder 公式解説)
- 区間の集合に要素を追加・削除し、集合の大きさの最大値とその個数を答える問題を、上の記事の方法で解いています。区間 chmin とは違う種類の作用で、作用が失敗する条件と、失敗の回数の評価をどう考えるかの例になります。Beats を使わない別解も載っています。
計算量の解析
Section titled “計算量の解析”- A simple introduction to “Segment tree beats”(jiry_2、Codeforces、英語)
- 考案者自身による紹介で、論文の 11 個の例題のうち 6 個(Task 1〜6)を扱っています。区間 chmin・chmax・加算に加え、各要素の過去の最大値などを扱う Historic Information の問題も含みます。再帰を打ち切る条件(break condition)と作用を載せる条件(tag condition)の枠組みと、ポテンシャルによる計算量の証明があります。
- 冒頭で著者自身が、計算量の議論に穴があると書いています。加算を混ぜた Task 2 は を示したうえで「たぶん のまま」と書いていますが、下の記事により と分かりました。
- Segment Tree Beats(ferin、HackMD)
- 上の jiry_2 の記事を日本語に訳したメモで、6 つの Task と計算量の解析を日本語で読めます。
- 実装が「ToDo」のままの節があるなど、未完成のメモです。Task 2 の「もしかしたら O(n log n) のままかも」は、今は否定されています。
- Segment Tree Beatsの計算量解析(37zigen、Scrapbox)
- 区間 chmin と区間和の場合に、償却 になることを図つきで証明しています。
- 後半の区間加算を混ぜる場合は、証明の途中の一文に著者が後から「(これは嘘)」と付けていて、代わりの議論はありません。後半の証明は不完全なものとして読んでください。
- The Time Complexity Lower Bound for Segment Tree Beats is log^2(Tony2_CF、Codeforces、英語)
- 区間加算と全体への chmax だけで 回の再帰が起きる入力を作り、加算を混ぜたときの計算量が であることを示した 2025 年の記事です。これを受けて、Library Checker の Range Chmin Chmax Add Range Sum にもこの入力のテストケースが追加されました。
- UOJ のブログに書かれた中国語の元記事を、Gemini 2.5 Pro で英語に機械翻訳したものです。
発展的な内容
Section titled “発展的な内容”- Segment Tree Beatsの実装メモ (応用的な例題まわり)(日々drdrする人のメモ)
- 区間の要素を「最大値」と「それ以外」に分けて別々に情報を持つ考え方で、jiry_2 の Task 3(値が変わった回数の和)と Task 4(2 つの列の和の最大値)を実装しています。
- Segment Tree Beatsの実装メモ (Historic Informationまわり)(日々drdrする人のメモ)
- 各要素の過去の最大値・最小値・和(Historic Information)を扱う方法です。過去の最大値と今の値の差を持つことで、区間加算を chmax に言い換えます。
- 図の説明の「xが最大値、yが二番目の最大値」と、
_update_dmaxの説明の「最大値・非最大値」は、どちらも「最小値」の誤りです(コードとそのコメントは正しいです)。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”Segment Tree Beats を扱う講座はまだありません。セグメント木・遅延セグ木を扱う AAL Contest 001: Let’s use segtree! でも、Segment Tree Beats は範囲外と明記されています。
AtCoder Library(ACL)に Segment Tree Beats はありません。
- Segment Tree Beats (based on atcoder::lazy_segtree)(hitonanode’s library)
- 上の「1行書き足すだけ」の記事の実装です。同じライブラリの
segmenttree/trees/に、区間 chmin・chmax・加算・和などのノードの例があります。
- 上の「1行書き足すだけ」の記事の実装です。同じライブラリの
- Segment Tree Beats(Luzhiled’s Library)
- ACL の遅延セグ木と同じような関数に、作用の失敗を表す
failを加えて渡す汎用の実装です。
- ACL の遅延セグ木と同じような関数に、作用の失敗を表す
- Range Chmin Chmax Add Update Range Min Max Sum Segment Tree Beats!(Nyaan’s Library)
- 区間 chmin・chmax・加算・代入と、区間最小値・最大値・和に特化した実装です。
百科事典・英語の資料
Section titled “百科事典・英語の資料”日本語版・英語版の Wikipedia と cp-algorithms には、Segment Tree Beats の項目も節もありません。
- Segment Tree Beats(USACO Guide、英語)
- 区間 mod(Codeforces 438D)と、Range Chmin Chmax Add Range Sum を、chmin だけ → 加算を追加 → chmax も追加、と段階を追って説明しています。コードは C++ で、練習問題の一覧もあります。
- 加算を混ぜたときの を「暫定的な上界」としていますが、今はこれで正しいと分かっています。
- 区间最值操作 & 区间历史最值(OI Wiki、中国語)
- 区間 chmin・chmax と Historic Information を、中国の OI の問題を例に説明しています。
- 国家集训队2016论文集(PDF、中国語)
- 吉如一の元の論文『区间最值操作与历史最值问题』が 99 ページから収録されています。
- Library Checker - Range Chmin Chmax Add Range Sum:区間 chmin・chmax・加算と区間和です。上のライブラリの多くがこの問題で verify されています。
- HDU 5306 - Gorgeous Sequence:区間 chmin と、区間最大値・区間和です。一番基本の形です。
- Codeforces 438D - The Child and Sequence:区間 mod、1 点代入、区間和です。mod を取ると値が変わらないか半分以下になることを使います。厳密には Beats ではありませんが、同じ考え方の入門としてよく挙げられます。
- ABC256 Ex - I like Query Problem:区間を にする操作、区間代入、区間和です。
- yukicoder No.880 - Yet Another Segment Tree Problem:区間代入、区間を にする操作、区間最大値・区間和です。
- ABC430 G - Range Set Modifying Query:区間の集合への要素の追加・削除と、集合の大きさの最大値とその個数です。