疎なkeyの順序を保ってdense indexへ圧縮する

概要

値が10億まであっても、入力に現れる値が数十万種類なら、10億要素の配列を用意する必要はない。登場する値だけを昇順に並べ、0から始まる連続した順位へ置き換えれば、値ごとの情報を小さな配列で管理できる。この変換を座標圧縮という。座標以外にも、点数・価格・時刻など、比較や検索に使う値に利用する。

ただし、順位の差は元の値の差を表さない。等しいか、どちらが小さいかを順位で判断し、距離や金額を計算するときは元の値を使う。 この役割分担を守ることで、値域が広い問題を、登場する値の種類数に応じた処理へ変えられる。

この単元では、圧縮表の作り方から、同じ値の集計、範囲の境界、将来の更新値、距離を残す場合までを扱う。圧縮後の配列を高速に集計するデータ構造は、後の単元へつなぐ。

考え方

値ごとの個数を、登場する値だけで管理する

列を左から読み、各位置で「それより前に現れた、自分以下の値の個数」を求めたいとする。例として、列 (40, 10, 40, 1000) を使う。

値をそのまま添字にすると、0から1000までの配列を用意することになる。しかし、更新する場所は10・40・1000だけである。大きさの順に並べて番号を付ければ、次の3要素で足りる。

元の値圧縮後の順位
100
401
10002

列は (1, 0, 1, 2) に変わる。ソートするのは対応表を作るための値のコピーであり、処理する列の順番は変えない。 また、二つの40は同じ順位1へ写すが、列の要素を一つに減らすわけではない。

順位0・1・2の出現数を並べた配列を、最初は (0, 0, 0) とする。ある値を読むたびに、その順位以下の個数を合計し、それから自分の順位の個数を1増やす。

読んだ値数えた個数追加後の出現数
400(0,1,0)
100(1,1,0)
402(1,2,0)
10003(1,2,1)

3個目の40では、以前の10と40の両方を数えるので2個になる。合計は5であり、元の列でも順位の列でも、添字 i<ji<j かつ値 Ai≤AjA_i\leq A_j を満たす組は同じ5組である。ここで AiA_i は元の列の ii 番目の値を表す。自分自身を数えないために、問い合わせてから追加する順序も守る。

ソートと重複除去が、大小関係と等値性を保存する

一般に、使う値をすべて集めてソートし、重複を取り除いた配列を XX とする。その要素数を KK とし、添字は0から始める。

X0<X1<⋯<XK−1X_0<X_1<\cdots<X_{K-1}

Xr=xX_r=x となる唯一の添字 rr を、値 xx の順位 rank⁡(x)\operatorname{rank}(x) と定める。先ほどの例では X=(10,40,1000)X=(10,40,1000) であり、rank⁡(40)=1\operatorname{rank}(40)=1 となる。この定義は、XX に含まれる値に対して使う。

ソート後の値は厳密に増加するため、登録された任意の二値 x,yx,y について、次が両方向に成り立つ。

x=y  ⟺  rank⁡(x)=rank⁡(y)x=y\iff\operatorname{rank}(x)=\operatorname{rank}(y)
x<y  ⟺  rank⁡(x)<rank⁡(y)x<y\iff\operatorname{rank}(x)<\operatorname{rank}(y)

したがって、元の値で大小や等しさを調べていた条件は、順位で同じように判定できる。比較する値の間に、入力に現れない整数が何個あるかは、この判定には関係しない。

圧縮表を作った後、各値の順位は XX 上の二分探索で求められる。具体的には、xx 以上の最初の要素の位置を返す lower_bound(X, x) を使う。xx が登録済みなら、その位置がちょうど順位になる。負数でも0でも、比較して並べられるなら同じ手順を使える。

値の範囲を、添字の区間へ写す

ここから、XX の先頭 tt 要素に対応する出現数の合計を P(t)P(t) と書く。つまり、順位が 0≤r<t0\leq r<t の要素を数える。P(0)=0P(0)=0 で、P(K)P(K) は現在の全要素数である。

登録済みの値 xx の順位が rr なら、xx 未満の個数は P(r)P(r)、xx 以下の個数は P(r+1)P(r+1) である。等号を含めるかどうかが、問い合わせる区間の端を一つ変える。

問い合わせの境界は、登録されていない値でもよい。lower_bound(X, x) は xx 未満の登録値の種類数、upper_bound(X, x) は xx 以下の登録値の種類数を返すので、その返り値をそのまま PP の引数にできる。

例えば X=(10,40,1000)X=(10,40,1000) に25は含まれないが、25未満の登録値は10だけなので、lower_bound(X, 25) は1である。表の最後の出現数 (1, 2, 1) なら、25未満の要素数は P(1)=1P(1)=1 になる。

下限 LL、上限 RR が L≤RL\leq R を満たすとする。半開区間 [L,R)[L,R)、すなわち L≤x<RL\leq x<R に入る要素数を考える。左端の位置を ℓ=lower_bound⁡(X,L)\ell=\operatorname{lower\_bound}(X,L)、右端の位置を u=lower_bound⁡(X,R)u=\operatorname{lower\_bound}(X,R) とすれば、答えは次になる。

P(u)−P(ℓ)P(u)-P(\ell)

右端も含む [L,R][L,R] なら、上の式の右端側だけ upper_bound(X, R) に変える。境界が最小値より小さければ返り値は0、最大値より大きければ KK となる。KK は要素の添字としては範囲外だが、区間の右端としては正しい。該当する値がなければ両端が同じ位置となり、差は0になる。

このように境界を二分探索で決めるだけなら、すべての問い合わせの境界値を圧縮表へ追加する必要はない。一方、その座標に情報を書き込むなら、書き込む場所として登録が必要になる。

将来使う値も集めてから、対応表を固定する

初期状態が10と40だけでも、後から25を挿入する操作があるなら、初めに10・25・40をまとめて圧縮する。初期値だけで対応表を作り、途中から25を差し込むと、40の順位が1から2へ変わってしまう。すでに配列へ保存した情報との対応が崩れる。

操作列が事前にすべて分かるなら、初期値と、追加・変更後に現れる値を先に集める。対応表を作った後は、操作を元の順番で実行する。先読みは添字を決めるためであり、問い合わせ時点で存在しない要素を先に有効にすることではない。

未知の値がオンラインで到着する場合、固定した圧縮表をそのまま使うことはできない。等値性だけが必要なら連想配列、大小関係も必要なら順序付きの集合や木などが候補になる。将来値を先読みできるかは、座標圧縮を選ぶ判断材料である。

距離を使うなら、順位と元の値を分けて持つ

10・40・1000の順位は0・1・2だが、元の差は30と960である。順位差はいずれも1なので、順位を引き算して長さを計算してはいけない。値の和・積・差・剰余・XORも、一般には保存されない。

距離が必要なら、XX を残しておく。順位 r,sr,s に対応する元の値の差は Xs−XrX_s-X_r で計算できる。順位を保存場所に使い、元の値を量の計算に使うのである。

特に、線分の被覆長や経過時間を数えるときは、圧縮した点と、その間の区間を区別する。端点が X0,…,XK−1X_0,\ldots,X_{K-1} なら、隣り合う端点の間には K−1K-1 個の区間がある。区間番号 rr は半開区間 [Xr,Xr+1)[X_r,X_{r+1}) を表し、その幅は Xr+1−XrX_{r+1}-X_r になる。

先ほどの対応表なら、区間0は [10,40)[10,40) で幅30、区間1は [40,1000)[40,1000) で幅960。両方を覆った長さは 30+960=99030+960=990 であり、区間数の2ではない。被覆数が正の区間だけ、その幅を加えれば元の長さを復元できる。

この表現が使えるのは、必要なすべての境界を集め、隣接する端点の間では被覆状態などの判定が変わらない場合である。整数の閉区間 [L,R][L,R] に含まれる整数を数えるなら、整数点 xx を単位区間 [x,x+1)[x,x+1) に対応させ、境界を L,R+1L,R+1 とする方法がある。この場合は R+1R+1 の整数幅にも注意する。

グリッドの移動では、元の隣接関係や障害物の間を通れるかも必要になる。点の順位が隣り合うことだけでは、元のマスが隣り合うとはいえない。周辺座標も残す設計や、間隔を辺の重みとして持つ設計など、移動の対応を別に確かめる必要がある。端点を集めるだけで任意の経路問題まで保存できるわけではない。

圧縮は、集計や探索を行うための準備になる

冒頭の出現数の例では、圧縮後の配列の先頭から毎回合計しても正しい。ただし、それでは問い合わせ一回が O(K)O(K) 時間である。Fenwick Treeによる重み付きprefix集約を使えば、一点への加算と先頭区間の合計を、それぞれ O(log⁡(K+1))O(\log(K+1)) 時間で扱える。圧縮は値域を小さくし、データ構造はその上の操作を速くする、という二段階を分けて考える。

ABC221 Eでは、部分列の両端の値の大小を調べながら、過去の添字に由来する重みを集計する。値を順位へ写せば、「今の値以下」という範囲をprefixとして問い合わせられる。同じ値の要素は同じ順位で重みを足し、取り出した位置の違いは重みに残す。公式解説の圧縮と集計がこの役割に対応する。

ABC231 Fでは、二つの値に関する不等式を同時に満たす組を数える。各軸の大小と等号は圧縮で保存できるが、等しい値をどの順に処理し、同じ組が複数あるとき何通りとして数えるかは別に決める必要がある。公式解説では、一方の軸で並べ、もう一方の軸をデータ構造で集計する。

ABC232 Gでは、円周上の必要な座標だけを残し、その間をまとめた辺に元の距離を持たせる。頂点番号を小さくしても、辺の重みまで1に置き換えることはできない。公式解説は、「不要な中間点を省くこと」と「その間を移動する費用を残すこと」を併用する例になっている。

ここまでは、必要な値や座標が分かっているところから始めた。これに対して、ABC374 Fのように、巨大な時刻の範囲から「最適解が使う候補時刻だけ」を先に導く問題もある。この候補の絞り込みには独立した証明が必要であり、順位を付ける操作だけでは得られない。候補発見は問題解説と公式解説で扱う。圧縮した後も、待ち時間や次に出荷できる時刻は元の時刻で計算する。

成立条件と計算量

使う前に、更新する値を事前に列挙できるか、圧縮後に何を判定・計算するかを確認する。比較だけなら順位で足りる。距離・金額・区間長も使うなら元の値や幅を持つ。経路を扱うなら、元の移動と圧縮後の移動が対応することまで示す。

集めた値が一つ以上ある場合を考え、圧縮表を作るために集めた値の総数を MM、重複除去後の種類数を KK、実行する更新・問い合わせの数を QQ とする。比較を定数時間で行える整数を扱う場合、ソートと重複除去は O(Mlog⁡(M+1))O(M\log(M+1)) 時間、二分探索による一つの値の順位取得は O(log⁡(K+1))O(\log(K+1)) 時間である。元の値の大きさそのものは、配列の要素数にならない。

圧縮後にFenwick Treeなどで各操作を対数時間で処理するなら、前処理を含む全体は

O(Mlog⁡(M+1)+Qlog⁡(K+1))O(M\log(M+1)+Q\log(K+1))

時間となる。全操作を保存してから圧縮する説明では、値の作業用配列と操作列も含め、全空間は O(M+Q+K)O(M+Q+K)。圧縮表とデータ構造の領域だけなら O(K)O(K) だが、先読みの保存領域を除いて全空間と呼ばない。

すべての値が等しければ K=1K=1 で、全要素は順位0へ集まる。入力に値が一つもなければ K=0K=0 なので、要素への更新はせず、空の範囲の集計を0として扱う。この場合は圧縮表の探索をせず、問い合わせ列を O(Q)O(Q) 時間で処理できる。重複除去は値の種類を減らす操作であり、元の要素数や重みまで減らす操作ではない。

状態の正規化では、問題上同じとみなせる対象を一つの形へまとめた。座標圧縮では、登録した異なる値を異なる順位へ写す。答えに必要な情報を選ぶという考え方は共通するが、圧縮したからといって値の異なる対象を同一視してよいわけではない。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。整列と二分探索を使い、大小関係と実際の距離を区別して添字化する。

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

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-coordinate-compression

習得する技能

  • 初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。

前提と範囲

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

直接の前提単元: なし。

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

保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。

このUnitでは扱わないもの

  • 値・時刻順にactive集合を増減するevent sweep、および固定配列・行列を入力順のまま読むだけのscan。

根拠