えびちゃんの日記

えびちゃん（競プロ）の日記です。

ポインタ木なしで償却 O(log(n)²) 時間の predecessor query

おつまみ記事

お風呂で思いついたシリーズです。

できる操作は次の通りです。

  • $\texttt{new}()$
    • $∅$ で初期化する
  • $S.\texttt{insert}(x)$
    • $S ← S ∪ \{x\}$ で更新する
  • $S.\texttt{remove}(x)$
    • $S ← S \smallsetminus \{x\}$ で更新する
  • $S.\texttt{less}(a)$
    • $\max {\{x∈S \mid x\lt a\}}$ を返す
  • $S.\texttt{lesseq}(a)$
    • $\max {\{x∈S \mid x\le a\}}$ を返す

これらについて、償却 $O(\log(n)^2)$ 時間で処理します。$n$ はその時点のクエリ数だったり、$|S|$ に改善できたりします。

基本方針

静的データ構造を $\log(n)$ 個持つことで動的にするテクです。

区間最小値を求めるセグ木を $\log(n)$ 個持ちます。 $i$ 番目のセグ木は、長さが $0$ または $2^i$ のいずれかです。

$S.\texttt{insert}(x)$ の際は、長さが $0$ となるセグ木のうち番号が最小のものが $i$ 番だとして、$[0\ldots i)$ 番目のセグ木の要素と $x$ を昇順に連結させたセグ木を $i$ 番目に置き、$[0\ldots i)$ 番目のセグ木は空にします。

$S.\texttt{remove}(x)$ の際は、セグ木上の二分探索を行うことで $x$ の検索を行うことができるため、見つかった場合は $∞$ で更新します。各セグ木について検索を行います。

$S.\texttt{less}(a)$ や $S.\texttt{lesseq}(a)$ の際は、各セグ木に対して二分探索を行い、条件を満たす最大の元（空の場合は無視）を集め、全体の最大値を求めます。

細部

有限値だけ見ると昇順に並んでいますが、$∞$ が入ることもあるので、気をつけて場合分けをします。

挿入の際、重複して要素を入れないように注意しましょう。入れたい場合も注意します。

$[0\ldots i)$ 番目のセグ木と $\{x\}$ を組み合わせるパートでは、マージソートで使うサブルーチンの要領で、ソート済みの列二つをソート済みになるように並べます。等比数列の和の形になるので、$O(2^i)$ 時間で可能です。 $i$ 番目のセグ木を作るためには $2^i$ 回の挿入が必要なため、セグ木の部分に関しては償却 $O(1)$ 時間です。 挿入操作の前に重複の確認が入り、$O(\log(n)^2)$ 時間です。

削除の際、$i$ 番目のセグ木に $∞$ が $2^{i-1}$ 個以上できた場合、$i-1$ 番目のセグ木の長さが $0$ であれば降格させるか、そうでない場合は統合させる（$i-1$ 番目のセグ木の要素とくっつけて $i$ 番目のセグ木を再構築する）こともできます。これにより、全体のうちの $∞$ が半分未満になるようにでき、管理する要素が $2|S|$ 程度で抑えられます。

successor query に対応させる場合、同じものを逆向きの比較関数で構築してもよいですし、隣り合う要素の添字を管理するなどで対応してもよいです。

実装

judge.yosupo.jp

すいません、Rust です。 本当は Python のことを考えて思いついたのですが、Python で実装して速くなる気がしなかったので実装していません。有志の方にお願いします。 案の定 Rust でも十分遅かったです。

普通に TLE すると思っていたんですが、9170 ms / 10 s で間に合ったのでうれしかったです。

その他

値の削除と predecessor query と要素の列挙が高速にできるデータ構造であれば、セグ木の部分は置き換えられそうです。

また、今回は各セグ木での答えの max を考えましたが、このようにいくつかに分割したものでの答えを組み合わせられるタイプのクエリであれば、別の種類のクエリにも答えられそうです。

例：Aho–Corasick のやつ

rsk0315.hatenablog.com

数年前に書いた記事ですが、手法はこれと同じです。他にも、binomial heap も似たような感じで $2^i$ サイズごとに分けたりしますね。

あとがき

ふとしたときに思いついた log 倍悪い系のデータ構造でした。他には、区間を管理するデータ構造をビットごとに持つことで RUQ するやつが（自分の中では）印象深いです。

rsk0315.hatenablog.com

これはお皿洗いしているときに思いついたシリーズでした。

浮動小数点数の記事はまだ時間がかかりそうです、すみません。

おわり

こういうふわっとした記事もいいですね。