区間monoid要約
概要
区間の答えを高速に求めるには、まず「隣り合う二つの区間について、何を覚えていれば全体の答えを作れるか」を決める。データ構造を選ぶ前に、要約する値と結合規則を設計する単元である。
区間monoid要約
区間の要約とは、区間全体を読み直さずに答えを求めるために保持する情報である。別の区間とつなぐときには、答えに使わない情報も必要になることがある。まず小さな例で、答えだけでは何が足りないかを考えよう。
考え方
文字列の区間内で、同じ文字が連続する長さの最大値を求めたい。左区間も右区間も答えが2でも、連結後の答えが2のままとは限らない。aa
と aa を合わせれば4になる一方、aa と bb なら2のままである。答えだけでは、境界をまたぐ連続部分を復元できない。
境界をまたいで伸びる長さを知るには、左区間の右端と右区間の左端で、それぞれ何文字続くかが必要になる。さらに、結合後の区間を次の結合にも使えるよう、各区間について次の六つを覚える。
| 要約 | 意味 |
|---|---|
len | 区間の長さ |
leftVal, rightVal | 両端の文字 |
pref, suff | 左端・右端から同じ文字が続く長さ |
best | 区間内で同じ文字が続く長さの最大値 |
左区間を 、右区間を とする。両区間が空でないとき、境界の文字が違えば全体の best
は左右の best の最大値。等しければ、境界をまたぐ
も候補になる。例えば baa と aab は境界でつながり、best が2から4になる。
全体の pref
が右区間へ伸びるのは、境界の文字が等しく、かつ左区間の全体が同じ文字のときだけ。その場合は
、それ以外は 。suff
は、境界の文字が等しく、右区間の全体が同じ文字なら
、それ以外は
となる。長さは和、両端の文字は外側の文字を引き継ぐ。これで六つの値がすべてそろい、元の文字列を参照せずに次の区間とも結合できる。
成立条件と計算量
要素一つの要約は len=pref=suff=best=1。空区間は len=0
とし、pref=suff=best=0 とする。どちらかが空区間なら、端の文字を比較する前に相手の要約をそのまま返す。空区間を左右のどちらにつないでも値が変わらないので、これが単位元になる。
この結合は、実際に二つの文字列を連結した結果の要約を正しく作る。三つの文字列について、先に左二つを連結しても、先に右二つを連結しても、できる文字列は同じである。したがって、実際の文字列から作った要約どうしでは、括る位置を変えても結果が変わらない。これが結合則の根拠になる。結合するたびに同じ意味の要約が得られ、結合則と単位元を持つ仕組みをmonoidという。
結合則で変えられるのは括る位置であり、左右の順序ではない。例えば aa の後に ab をつなぐと best は3だが、ab の後に aa をつなぐと2になる。Segment Treeでも、取得した区間を元の順序で結合する。
Segment Treeの各葉には一文字の要約を置き、各内部節点には左の子と右の子をこの順に結合した要約を置く。一点更新では葉を置き換えて根まで再計算し、区間取得では対象区間を覆う節点の要約を左から順に結合して、最後の best を答えとする。区間の分解と取得手順は概念上の親単元で確認できる。
この例の要約サイズ・結合費用は定数なので、Segment Treeの構築は 、一点更新と区間取得は各 、空間は 。ここで は文字列の長さである。一般に要約サイズを 、結合費用を とすると、葉の要約を用意した後の構築は 、一点更新と区間取得は各 、空間は になる。葉の要約の生成費用は別に数え、要約が大きい問題では結合を定数時間とみなさない。
復習では、答えだけで結合できない反例、境界に必要な情報、単位元、結合則の根拠を言葉にする。ABC223 Fでは括弧列、ABC331 Fでは両向きのhashを、次の区間とも結合できる形に要約する。下の主配置問題から進み、関連問題は他の主題との組合せを確認するときに使う。
問題一覧
- ABC432 E「Clamp」 公式問題
- ABC343 F「Second Largest Query」 公式問題
- ABC223 F「Parenthesis Checking」 公式問題
- ABC415 F「Max Combo」 公式問題
- ABC424 F「Adding Chords」 公式問題組合せ: 円環順序・chord交差
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: 区間monoid要約 / 補助タグ: 円環順序・chord交差
- ABC331 F「Palindrome Query」 公式問題
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 列・文字列のrolling fingerprint(順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 区間monoid要約 / 補助タグ: 列・文字列のrolling fingerprint
- ABC285 F「Substring of Sorted String」 公式問題
- ABC429 F「Shortest Path Query」 公式問題
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 半環行列・min-plus/max-min遷移(遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。) / 最短路モデル(DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。)。主タグ: 区間monoid要約 / 補助タグ: 半環行列・min-plus/max-min遷移、最短路モデル
- ABC460 F「Farthest Pair Query」 公式問題
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 基準点からの木距離・剰余類・直径・中心(一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。)。主タグ: 区間monoid要約 / 補助タグ: ancestor query・LCA、木距離・直径・中心・最遠点
- ABC440 F「Egoism」 公式問題組合せ: 交換論から選択順を導く
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 区間monoid要約 / 補助タグ: 貪欲法と交換論
- ABC292 Ex「Rating Estimator」 公式問題
- ABC447 G「Div. 1 & Div. 2」 公式問題組合せ: event順にactive集合を更新する
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 区間monoid要約 / 補助タグ: event・値順のオフライン走査
- ABC418 F「We're teapots」 公式問題
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 区間monoid要約 / 補助タグ: ordered set・multisetの動的順序管理
- ABC365 F「Takahashi on Grid」 公式問題
- ABC246 Ex「01? Queries」 公式問題組合せ: 列・subsequence DP
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。主タグ: 区間monoid要約 / 補助タグ: 列・subsequence DP
- ABC434 G「Keyboard」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC248 Ex「Beautiful Subsequences」 公式問題
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: 単調stack・queueによる支配候補の削除 / 補助タグ: 遅延評価する区間作用、区間monoid要約
- ABC254 F「Rectangle GCD」 公式問題主題: gcd不変量・差分構造
技能・出典
主題: gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: gcd不変量・差分構造 / 補助タグ: 区間monoid要約
- ABC262 F「Erase and Rotate」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC265 G「012 Inversion」 公式問題主題: 区間更新を要約へ作用させる
技能・出典
主題: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 遅延評価する区間作用 / 補助タグ: 区間monoid要約
- ABC266 Ex「Snuke Panic (2D)」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC283 F「Permutation Distance」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換、区間monoid要約
- ABC299 G「Minimum Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC309 F「Box in Box」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC322 F「Vacation Query」 公式問題主題: 区間更新を要約へ作用させる
技能・出典
主題: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 遅延評価する区間作用 / 補助タグ: 区間monoid要約
- ABC339 E「Smooth Subsequence」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 区間monoid要約
- ABC353 G「Merchant Takahashi」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。 max_j(dp[j]−C|j−t|)+pを、j≤tのmax(dp[j]+Cj)−Ct+pとj≥tのmax(dp[j]−Cj)+Ct+pへ分ける。二本の区間最大で各イベントO(log N)。主タグ: DP遷移の集約・高速化 / 補助タグ: 区間monoid要約
- ABC354 F「Useless for LIS」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC356 F「Distance Component Size Query」 公式問題
技能・出典
主題: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: ordered set・multisetの動的順序管理 / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC357 F「Two Sequence Queries」 公式問題主題: 区間更新を要約へ作用させる
技能・出典
主題: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 遅延評価する区間作用 / 補助タグ: 区間monoid要約
- ABC360 G「Suitable Edit for LIS」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC388 G「Simultaneous Kagamimochi 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: 単調境界探索 / 補助タグ: 区間monoid要約、尺取り法・sliding window
- ABC408 F「Athletic」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。 dp[p_h]=1+max_{|j−p_h|≤R,H_j≤h−D}dp[j]。高さ順にeligibleな点だけを有効化し、残る位置条件を区間最大にする。二条件の全点走査がsortとO(N log N)の更新・取得になる。主タグ: DP遷移の集約・高速化 / 補助タグ: event・値順のオフライン走査、区間monoid要約
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 値域集約による部分列DP / 補助タグ: event・値順のオフライン走査、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC437 F「Manhattan Christmas Tree 2」 公式問題主題: 幾何の基本判定と座標変換
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 区間monoid要約
- ABC453 G「Copy Query」 公式問題
技能・出典
主題: 永続data structure・structural sharing(変更pathだけを複製して未変更部分を共有し、各versionのrootから過去状態へアクセスする。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 永続data structure・structural sharing / 補助タグ: 区間monoid要約
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。十分な要約と結合演算を定義し、Segment Treeへ正しく載せる。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 結合的な区間要約・区間分解・合成。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-range-monoid-aggregation
習得する技能
- 答えだけでは結合できない反例から、次の結合にも必要な情報を導く。
- 空区間の扱いと左右の結合順を定め、結合則が成り立つ根拠を説明する。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 値域集約による部分列DP、動的・implicit Segment Tree、冪等演算のoverlap range query・Sparse Table、区間更新を要約へ作用させる、Segment Tree Beats、Segment Treeのcanonical区間分解、SWAG・two-stack queue aggregation。
この単元では要約と結合の設計を扱う。左から順に一つの要約へ畳み込むprefix foldや、SWAGにも同じ結合規則を使える。区間全体への更新と要約を両立させる条件は、区間更新を要約へ作用させるで扱う。
このUnitでは扱わないもの
- 区間monoid要約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。