ordered set・multisetの動的順序管理

概要

整数を追加・削除しながら、「この値以上で最小の要素」「今の最小値」「小さい方から一定個数の和」などを求めたい。毎回ソートすれば順序は分かるが、一要素しか変わらない更新に対して全体を並べ直すのは無駄が多い。

順序付き集合は、挿入・削除の後も比較順を保ち、必要な境界へ直接移動するための道具である。同じ値を複数個残す場合は多重集合を使う。この単元では、境界探索を出発点に、隣接対の局所更新と、二集合による順位の境界の維持へ進む。答えを速く得られる理由は、木構造の名前ではなく、何を集合へ入れ、どの不変条件を保つかから説明する。

考え方

毎回ソートする処理の、何を省きたいか

多重集合に (2,6,6,12)(2,6,6,12) があるとする。新しく8を入れても、2、二個の6、12の相対順は変わらない。探す必要があるのは8の入る位置であり、全要素の順序を再計算する必要はない。

平衡二分探索木は、各節点の左右に小さい値・大きい値を置き、高さを対数に保つことで、この位置探索と更新を高速に行う。典型的なインターフェースが、値 xx 以上の先頭を返す lower_bound(x) と、xx より大きい先頭を返す upper_bound(x) である。

操作(2,6,6,12)(2,6,6,12) での結果
lower_bound(6)最初の6
upper_bound(6)12
lower_bound(8)12
最初の6の直前2
二個目の6の直前一個目の6

ここで「6より小さい最大値」と「ある一個の6の直前」は違う。値の条件の境界を求めるのか、実際の一要素の隣を求めるのかを分ける。

同じ値の個数が意味を持つなら、重複を一つへまとめる set では足りない。multiset を使うか、値と一意なIDの組を順序付き集合に入れる。C++で一個だけ削除するなら、見つけた要素のイテレータを erase へ渡す。値を直接渡すと同値要素を全部消すためである。

隣接関係を辺として考える

昇順に並ぶ値の間の差をすべて管理したいとする。(2,6,12)(2,6,12) では隣接差は4と6。ここへ8を入れると、6と12の間の差6が消え、差2と4が生まれる。2と6の間の差4は変わらない。

値の列:  2 ── 6 ───── 12
                 ↓ 8を挿入
値の列:  2 ── 6 ─ 8 ─ 12

挿入位置の左右を l,rl,r、隣接対の情報を f(l,r)f(l,r) とすると、消すのは f(l,r)f(l,r) 一個、足すのは f(l,x),f(x,r)f(l,x),f(x,r) の各一個だけである。削除では逆に、対象に接する二本を消し、左右がそろっていればつなぎ直す。先頭・末尾なら存在する辺だけを扱う。

隣接差の最大値を求めるなら、元の値の多重集合に加え、各辺の差の多重集合を持つ。上の挿入後は候補が (2,4,4)(2,4,4) になる。もともと4があっても、新たに生じた4は別の辺なので一個追加する。一辺を消すときも一個だけ消す。元の要素数が nn なら、候補の個数は max⁡(n−1,0)\max(n-1,0) である。

同じ構造を隣接XORへ使うのがABC308 Gである。ただし、全対の最小XORが隣接対から得られることは、別に最高相違ビットから証明する必要がある。「隣接情報を速く更新できる」と「隣接だけ見れば元の答えが出る」を混同しない。

答えが辺の情報の総和なら、候補の多重集合の代わりに一つの総和を持ち、消える分を引いて生まれる分を足せばよい。必要な取得操作に合わせて、補助情報の持ち方を選ぶ。

小さい側を丸ごと保存し、順位の境界だけ動かす

次に、小さい方から kk 個の和を毎回求めたいとする。順序付き集合でも、先頭から kk 個を毎回走査すると O(k)O(k) かかる。そこで、その kk 個そのものを別の多重集合 LL に保存し、残りを RR に置く。さらに LL の和 ss を持つ。

全体の要素数を nn とし、次の三つを保つ。

∣L∣=min⁡(k,n)|L|=\min(k,n)
max⁡(L)≤min⁡(R)(両方が非空なら)\max(L)\leq\min(R)\quad\text{(両方が非空なら)}
s=∑x∈Lxs=\sum_{x\in L}x

個数が合い、すべての LL の値が RR の値以下なら、LL は小さい方の必要個数をちょうど含む。境界に同じ値がある場合は、どの一個を左へ置いても和は同じである。

k=2k=2 として、集合 (2,5,5,11)(2,5,5,11) から追う。

段階LLRRss
初め(2,5)(2,5)(5,11)(5,11)7
1をいったん左へ追加(1,2,5)(1,2,5)(5,11)(5,11)8
左の最大5を右へ移動(1,2)(1,2)(5,5,11)(5,5,11)3
左の2を削除(1)(1)(5,5,11)(5,5,11)1
右の最小5を左へ移動(1,5)(1,5)(5,11)(5,11)6

全体の順序を作り直す代わりに、必要な個数の境界をまたぐ一要素だけを動かしている。

空の二集合と和0から始める。一要素の追加では、LL が非空で追加値が max⁡(L)\max(L) 以下なら左へ、それ以外なら右へ入れる。削除では左にあれば一個消し、なければ右から一個消す。左の変更では和も同時に足し引きする。

その後、左が目標個数より多ければ左の最大を右へ、少なければ右の最小を左へ移す。移動のたびに ss を更新する。挿入時の振り分けで境界順は保たれ、削除も残る要素の順序を壊さないため、個数を直せば三条件を回復できる。

固定 kk で一要素を更新すると、個数のずれは高々1なので移動は定数回で済む。k=0k=0 なら左は常に空で和0、k>nk>n なら全要素を左へ置く。同じ値が両集合にあっても、値だけを扱う問題では左の一個を削除してから補充してよい。特定の個体を区別する問題では、IDもキーに含めて所属を追う。

大きい kk 個の和は大小を反転して同じ考え方を使える。ABC306 Eでは上位側の和を更新し、ABC281 Eでは移動窓から出る一個の削除と入る一個の追加を組み合わせる。

求める情報から道具を選ぶ

最小値を取り出すだけなら優先度付きキューも候補になる。任意の値の削除や、ある値の前後を直接求めたいときに、順序付き集合が役立つ。更新がなく全質問も分かっていれば、ソートと走査の方が簡単なこともある。

標準の set・multiset は、値による境界探索をしてくれるが、任意の順位へ直接飛ぶ機能は持たない。必要なのが固定個数の境界なら二集合、任意の順位や値域内の個数・総和なら、座標圧縮とFenwick Treeなどを検討する。lower_bound の結果まで distance で数えると、木のイテレータでは線形時間になる点に注意する。

成立条件と計算量

比較規則が処理中に変わらず、要素どうしに一貫した順序を与えられることが前提である。外部の可変値を比較関数から参照し、集合へ入れたまま順序を変えてはいけない。値を更新する場合は旧要素を削除して新要素を挿入する。

平衡木で要素数を nn とすると、挿入、値の探索、値を探して一個削除する処理は各 O(log⁡n)O(\log n) 時間、保存領域は O(n)O(n)。最小・最大を保持する標準的な実装では端の取得は定数時間である。空集合や、先頭の前・末尾の後は参照できない。該当する境界がない場合の戻り値も確認する。

隣接候補の維持では一更新あたり定数本、固定 kk の二集合では定数回の境界移動しか起きないので、いずれも一更新は O(log⁡n)O(\log n)、答えの取得は O(1)O(1)。全 QQ 更新で要素数が高々 QQ なら、全体で O(Qlog⁡Q)O(Q\log Q) 時間・O(Q)O(Q) 空間となる。kk 自体を一度に大きく変える場合は、移動個数も評価へ加える。

和には要素の絶対値と個数の積を格納できる整数幅を使う。単独の値が32 bitに収まっても、和まで収まるとは限らない。復習では、求めたい境界、保つ個数、保存する集約値の三つを言葉で定義してから、更新の前後でそれらが保たれるかを追う。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。前後要素・重複を管理し、二集合に分けて境界と集計値を保つ基本操作を学ぶ。

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

概念上の親: heap・ordered setで全候補の極値を保つ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-ordered-set-multiset

習得する技能

  • 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: 端点更新型のrun分割管理。

比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • ordered set・multisetの動的順序管理の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠