区間monoid要約

概要

区間の答えを高速に求めるには、まず「隣り合う二つの区間について、何を覚えていれば全体の答えを作れるか」を決める。データ構造を選ぶ前に、要約する値と結合規則を設計する単元である。

区間monoid要約

区間の要約とは、区間全体を読み直さずに答えを求めるために保持する情報である。別の区間とつなぐときには、答えに使わない情報も必要になることがある。まず小さな例で、答えだけでは何が足りないかを考えよう。

考え方

文字列の区間内で、同じ文字が連続する長さの最大値を求めたい。左区間も右区間も答えが2でも、連結後の答えが2のままとは限らない。aa と aa を合わせれば4になる一方、aa と bb なら2のままである。答えだけでは、境界をまたぐ連続部分を復元できない。

境界をまたいで伸びる長さを知るには、左区間の右端と右区間の左端で、それぞれ何文字続くかが必要になる。さらに、結合後の区間を次の結合にも使えるよう、各区間について次の六つを覚える。

要約意味
len区間の長さ
leftVal, rightVal両端の文字
pref, suff左端・右端から同じ文字が続く長さ
best区間内で同じ文字が続く長さの最大値

左区間を AA、右区間を BB とする。両区間が空でないとき、境界の文字が違えば全体の best は左右の best の最大値。等しければ、境界をまたぐ A.suff+B.prefA.\mathrm{suff}+B.\mathrm{pref} も候補になる。例えば baa と aab は境界でつながり、best が2から4になる。

全体の pref が右区間へ伸びるのは、境界の文字が等しく、かつ左区間の全体が同じ文字のときだけ。その場合は A.len+B.prefA.\mathrm{len}+B.\mathrm{pref}、それ以外は A.prefA.\mathrm{pref}。suff は、境界の文字が等しく、右区間の全体が同じ文字なら A.suff+B.lenA.\mathrm{suff}+B.\mathrm{len}、それ以外は B.suffB.\mathrm{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の構築は O(N)O(N)、一点更新と区間取得は各 O(log⁡N)O(\log N)、空間は O(N)O(N)。ここで NN は文字列の長さである。一般に要約サイズを ss、結合費用を TT とすると、葉の要約を用意した後の構築は O(NT)O(NT)、一点更新と区間取得は各 O(Tlog⁡N)O(T\log N)、空間は O(Ns)O(Ns) になる。葉の要約の生成費用は別に数え、要約が大きい問題では結合を定数時間とみなさない。

復習では、答えだけで結合できない反例、境界に必要な情報、単位元、結合則の根拠を言葉にする。ABC223 Fでは括弧列、ABC331 Fでは両向きのhashを、次の区間とも結合できる形に要約する。下の主配置問題から進み、関連問題は他の主題との組合せを確認するときに使う。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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要約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠