コンテンツにスキップ

Segment Tree Beats

タグ「Segment Tree Beats」の記事 1 件

Segment Tree Beats のリンク集

Segment Tree Beats について、参考になる記事や資料をまとめました。

Segment Tree Beats(Segment Tree Beats!、中国では「吉老师线段树」とも)は、2016 年ごろに吉如一(jiry_2)が中国の国家集訓隊論文で発表した、遅延評価セグメント木の拡張です。区間 chmin(ai←min⁡(ai,x)a_i \leftarrow \min(a_i, x))のように、遅延セグ木にそのままでは載らない作用を扱えます。名前はアニメ「Angel Beats!」に由来します。

考え方は「ノードへの作用が計算できないときは、子に再帰して計算し直す」というものです。区間 chmin と区間和の場合、各ノードに最大値・厳密に 2 番目に大きい値・最大値の個数・和を持ちます。xx が最大値以上なら何もせず、2 番目の値より大きければ最大値だけが xx に変わるので和もすぐ更新でき、それ以外のときだけ子に再帰します。再帰が起きる回数をポテンシャルで抑えるのがこの手法の要で、問題ごとに作用の設計と計算量の解析が必要です。

計算量は次のとおりです。

  • 区間 chmin・chmax と区間和だけなら、全体で償却 O((N+Q)log⁡N)O((N+Q) \log N) です。
  • 区間加算も混ぜると O((N+Q)log⁡2N)O((N+Q) \log^2 N) です。O((N+Q)log⁡N)O((N+Q) \log N) のままではないかという予想もありましたが、2025 年に Ω(Nlog⁡2N)\Omega(N \log^2 N) になる入力が見つかり、Θ(log⁡2)\Theta(\log^2) と分かりました。古い資料では「もしかしたら O(log⁡)O(\log) かも」と書かれていることがあります。
  • Segment Tree Beatsの実装メモ (基本まわり)(日々drdrする人のメモ)
    • 区間 chmin と区間最大値・区間和(HDU 5306 Gorgeous Sequence)、区間 chmin・chmax の場合を、図つきで実装の流れに沿って説明しています。ノードに何を持ち、どの条件で再帰を打ち切るかが分かります。最後に区間加算・区間代入を混ぜる場合にも少し触れています。計算量の解析は含みません。コードは C++ です。
    • コードの区間最大値は範囲外で 00 を返すので、負の値がある問題ではそのままでは使えません。
  • ABC256 Ex - I like Query Problem の解説(Nyaan、AtCoder 公式解説)
    • 区間を ⌊ai/x⌋\lfloor a_i / x \rfloor にする操作を含む問題で、解法 2 として Segment Tree Beats を説明しています。ACL の lazy_segtree の実装を土台に、作用が「失敗」したら子に再帰するように拡張する、という説明で、遅延セグ木を書ける人には一番入りやすい資料です。各ノードに「区間の値がすべて等しいか」のフラグを持ち、値が半分以下になることを使ったポテンシャルで O((N+Qlog⁡N)log⁡max⁡A)O((N + Q \log N) \log \max A) を示しています。
  • 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)は切れています。
  • ABC430 G - Range Set Modifying Query の解説(kyopro_friends、AtCoder 公式解説)
    • 区間の集合に要素を追加・削除し、集合の大きさの最大値とその個数を答える問題を、上の記事の方法で解いています。区間 chmin とは違う種類の作用で、作用が失敗する条件と、失敗の回数の評価をどう考えるかの例になります。Beats を使わない別解も載っています。
  • 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 は O(nlog⁡2n)O(n \log^2 n) を示したうえで「たぶん O(nlog⁡n)O(n \log n) のまま」と書いていますが、下の記事により Θ(nlog⁡2n)\Theta(n \log^2 n) と分かりました。
  • Segment Tree Beats(ferin、HackMD)
    • 上の jiry_2 の記事を日本語に訳したメモで、6 つの Task と計算量の解析を日本語で読めます。
    • 実装が「ToDo」のままの節があるなど、未完成のメモです。Task 2 の「もしかしたら O(n log n) のままかも」は、今は否定されています。
  • Segment Tree Beatsの計算量解析(37zigen、Scrapbox)
    • 区間 chmin と区間和の場合に、償却 O(log⁡n)O(\log n) になることを図つきで証明しています。
    • 後半の区間加算を混ぜる場合は、証明の途中の一文に著者が後から「(これは嘘)」と付けていて、代わりの議論はありません。後半の証明は不完全なものとして読んでください。
  • The Time Complexity Lower Bound for Segment Tree Beats is log^2(Tony2_CF、Codeforces、英語)
    • 区間加算と全体への chmax だけで Ω(nlog⁡2n)\Omega(n \log^2 n) 回の再帰が起きる入力を作り、加算を混ぜたときの計算量が Θ(nlog⁡2n)\Theta(n \log^2 n) であることを示した 2025 年の記事です。これを受けて、Library Checker の Range Chmin Chmax Add Range Sum にもこの入力のテストケースが追加されました。
    • UOJ のブログに書かれた中国語の元記事を、Gemini 2.5 Pro で英語に機械翻訳したものです。
  • Segment Tree Beatsの実装メモ (応用的な例題まわり)(日々drdrする人のメモ)
    • 区間の要素を「最大値」と「それ以外」に分けて別々に情報を持つ考え方で、jiry_2 の Task 3(値が変わった回数の和)と Task 4(2 つの列の和の最大値)を実装しています。
  • Segment Tree Beatsの実装メモ (Historic Informationまわり)(日々drdrする人のメモ)
    • 各要素の過去の最大値・最小値・和(Historic Information)を扱う方法です。過去の最大値と今の値の差を持つことで、区間加算を chmax に言い換えます。
    • 図の説明の「xが最大値、yが二番目の最大値」と、_update_dmax の説明の「最大値・非最大値」は、どちらも「最小値」の誤りです(コードとそのコメントは正しいです)。

Segment Tree Beats を扱う講座はまだありません。セグメント木・遅延セグ木を扱う AAL Contest 001: Let’s use segtree! でも、Segment Tree Beats は範囲外と明記されています。

AtCoder Library(ACL)に Segment Tree Beats はありません。

日本語版・英語版の Wikipedia と cp-algorithms には、Segment Tree Beats の項目も節もありません。

  • Segment Tree Beats(USACO Guide、英語)
    • 区間 mod(Codeforces 438D)と、Range Chmin Chmax Add Range Sum を、chmin だけ → 加算を追加 → chmax も追加、と段階を追って説明しています。コードは C++ で、練習問題の一覧もあります。
    • 加算を混ぜたときの O((n+q)log⁡2n)O((n+q) \log^2 n) を「暫定的な上界」としていますが、今はこれで正しいと分かっています。
  • 区间最值操作 & 区间历史最值(OI Wiki、中国語)
    • 区間 chmin・chmax と Historic Information を、中国の OI の問題を例に説明しています。
  • 国家集训队2016论文集(PDF、中国語)
    • 吉如一の元の論文『区间最值操作与历史最值问题』が 99 ページから収録されています。