考察
挿入するたびに後ろの要素を動かす代わりに、最終的な列の枠を先に用意し、後から挿入した値から位置を確定する。後続の挿入は既存要素の相対順を変えないので、未確定の枠だけを数えれば、挿入時の順位をそのまま使える。
配列へ前から直接挿入すると、1回で最大 個の要素をずらす。毎回先頭へ挿入する場合は全体で となり、 では間に合わない。ここで、値 を入れた瞬間の位置と、全挿入後の位置を区別する。前者は として分かっているが、後者は後続の挿入でずれる。
最終列から値 を取り除くと、値 の相対順は 回目の挿入直後と一致する。従って、大きい値を既に最終位置へ置いた時点では、残る空き枠が値 の場所に対応し、値 の最終位置は左から 番目の空き枠になる。
公式入力例1の では、前向きの列は次のように変わる。
逆向きでは、枠の番号を最終列の左から として、次の順に埋める。「空き枠の順位」と「最終列の位置」は異なることに注意する。
例えば値3を置くとき、枠1の値4を数えず、残る枠2・3・4のうち2番目を選ぶ。これが前向きの列 における値3の順位2に対応する。
空き枠を1、埋まった枠を0とする長さ の列 を Fenwick Tree で管理する。全て1で初期化し、 の順に、接頭辞和が 以上になる最小位置 を探す。答えの 番目に値 を書き、 を1から0へ更新する。最後に答えを左から出力する。
この順位探索は、接頭辞和を取得しながら外側で位置を二分探索すると1回 かかる。Fenwick Tree 内の区間和を直接使えば、1回 にできる。1始まりの内部配列を tree とし、探索中は「既に読み飛ばした接頭辞の末尾」 と「その右側で探す残り順位」 を保つ。初期値は である。
以下の最大の2の冪を として、大きい桁から を半分ずつにする。 なら tree[q] を調べる。この探索順では が の倍数なので、tree[q] はちょうど区間 の空き枠数を表す。その個数が 未満なら、探す枠は区間の右にある。区間全体を飛ばして とし、その個数を から引く。個数が 以上なら、探す枠は区間内にあるので飛ばさず、次の小さい桁を調べる。範囲外の も飛ばさない。
全桁を調べると、 は接頭辞和が 未満である最後の位置になり、答えは である。各桁で区間和を一つ読むだけなので、探索全体は になる。
典型の発動条件
操作の逆転
逐次挿入で位置が広くずれても、既存要素同士の相対順が保存されるなら、後から挿入した要素を除いて過去の列を復元できる。最終枠を固定し、逆順に未確定枠の順位を使う方法が候補になる。
Fenwick treeのk-th search
動的な非負の頻度列で、累積個数が指定順位に達する最初の位置を求めたいときに使う。非負だから接頭辞和が単調になり、区間個数と残り順位の比較で区間全体を読み飛ばせる。負の頻度を許すと、この探索の前提が崩れる。
問題固有の要素
値 がそのまま挿入時刻を表すため、値の降順に最終位置を決められる。 は固定された位置ではなく、その時点で残る空き枠の順位として読み替える。この対応によって、前向きの位置ずれを明示的に処理する必要がなくなる。
正当性
後続の挿入は既存要素の相対順を変えない。従って、最終列から値 を取り除いた残りの列は、 回目直後の列と一致する。
逆順で値 を置く直前に、値 は正しい最終位置にあり、空き枠を左から見た順序は 回目直後の列の各要素に対応する、という不変条件を保つ。初めの では全枠が空いており、この対応が成り立つ。 回目直後の列では値 は 番目なので、不変条件より 番目の空き枠がその正しい最終位置である。
その枠を埋めて空き枠から除くと、値 を取り除いた順序、すなわち 回目直後の列との対応が残る。よって不変条件は次にも保たれる。空き枠はちょうど 個あり、 なので選ぶ枠も必ず存在する。全ての値を置き終えると、全枠が正しい最終列になる。
実装上の注意
- は1始まりの順位である。上の内部探索が得る は答えの一つ手前なので、選ぶ位置は 。答え配列が0始まりなら変換する。
- 区間を飛ばせる条件は空き枠数が残り順位「未満」であること。等しいときに飛ばすと、求める枠も通り過ぎる。
- 1始まりの
tree[q] は末尾から q & -q 個の和を持つ。全1の列なら tree[q] = q & -q として で構築できる。選んだ位置には通常の点加算で を反映する。
復習の核
- 挿入が位置をずらしても相対順を保つなら、後から挿入した値を除いた列と、過去の列を対応させる。
- 「空きが足りる」だけでは順位を使う証明にならない。未確定枠の順序が何と一致するかを言葉にする。
- Fenwick 内の順位探索では、飛ばした接頭辞と残り順位を保つ。接頭辞和の外側二分探索とは計算量が異なる。
計算量と制約
時間
全1の Fenwick Tree の構築は 。各値について順位探索と点更新をそれぞれ で行い、出力に かかるので、全体で 。通常は と表すが、ここでは の定数時間も含めた。
空間
入力の 、答え配列、Fenwick Tree をそれぞれ長さ で保持するので 。
制約との対応
公式制約は 、。空き枠の頻度は常に0または1であり、順位探索に必要な接頭辞和の単調性が保たれる。 なら最左の空き枠、 なら最右の空き枠を選び、 も同じ手順で処理できる。
出典