small-to-large・DSU on Tree

概要

小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。

重複も保持する併合で小さい側を大きい側へ移すと、移った要素の所属サイズは少なくとも倍増し、一要素O(log N)回しか移らない。重複を消すsetではこの倍増をそのまま使えない。重複が小さい側の半数以上なら走査費用を消える要素へ課金し、それ未満なら生存要素へ課金する。後者では併合後サイズが小さい側の3/2倍を超えるので、生存への課金も一要素O(log N)回となる。

ABC324 Gの分割は、分割前の各要素が一方だけに属し、小さい側だけを走査するから、走査された要素の所属サイズが半減する。併合の倍増、setの消滅、分割の半減で何を数えているかを区別し、操作一回あたりのデータ構造費用を最後に掛ける。

考え方

二つの集合を併合するとき小さい側の要素だけ大きい側へ移す。移動した要素の所属集合サイズは少なくとも倍になるため、各要素の移動回数はO(log N)に抑えられる。

重複を消すsetでは、併合する二つの物理サイズをs≤tとし、消える重複数をdとする。d≥s/2なら小さい側s個の走査費用をd個の消滅へ課金でき、各物理要素の消滅は一度。d<s/2なら併合後サイズはt+s−d>t+s/2≥3s/2なので、小さい側の生存要素の所属サイズが少なくとも3/2倍になる。この場合の走査費用は生存要素へ定数倍で課金でき、各要素が負担する回数はO(log N)。両場合を合わせて総走査O(N log N)となる。

集合を分割するときは逆に小さい側だけを列挙・構築し、大きい側のcontainerを再利用する。列挙された要素の所属サイズが半分以下になるので、要素が新たに生成されず再併合もない操作列なら同じ対数回の課金ができる。分割と併合を交互に許す操作列ではサイズが戻るので、この証明だけでは足りない。

成立条件と計算量

挿入O(1)なら総O(N log N)、平衡木で挿入O(log N)ならO(N log² N)。重複keyを統合して物理サイズが増えない場合、要素数や重みなど適切な課金量を別に定める。代表集合の所有権を交換して不要なコピーを避ける。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。併合時の倍増と分割時の半減を使い、重複が消える場合も総走査量を証明する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 軽重分類と償却解析で総仕事量を抑える。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-small-to-large

small-to-large・DSU on Tree

習得する技能

  • 小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • small-to-large・DSU on Treeの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠