Day 121-Q3 — Y-fast Trie（successor/predecessorの高速データ構造）

2026-08-13 赤色 Master / Phase 8+ ★★★★★★★★★ データ構造・バケット分割・successor/predecessor

問題

値域 $[0, U)$（$U = 2^{20}$）の整数集合を管理し、Q個のクエリを順に処理せよ。

  • I x: 集合に $x$ を追加する（既に存在する場合は何もしない）
  • D x: 集合から $x$ を削除する（存在しない場合は何もしない）
  • S x: $x$ より真に大きい最小の要素（successor）を出力。無ければ -1
  • P x: $x$ より真に小さい最大の要素（predecessor）を出力。無ければ -1

入力形式

Q
query_1
...
query_Q

制約

$1 \le Q \le 2\times10^5$
$0 \le x < 2^{20}$

入出力例

入力例1

8
I 3
I 7
I 9
I 14
S 5
P 10
I 6
S 5

出力例1

7
9
6

入力例2（直前の状態から継続）

2
D 7
S 6

出力例2

9

概念図: 代表元だけを俯瞰しバケット内部を分業する

値域を幅2^10のバケットに分割し、代表元だけを俯瞰する bucket 0 bucket 1 bucket 2 bucket 3 非空 → 代表元リストへ 空 → 代表元なし 非空 → 代表元リストへ 空 → 代表元なし 代表元リスト(bisectで二分探索): [0, 2] successor(x)はまず同じバケット内、無ければ代表元リストで次のバケットを探す

ヒント（段階的開示）

ヒント1: 方向性
X-fast Trie（ビット文字列トライ+各レベルのハッシュテーブル）はsuccessor/predecessorを$O(\log\log U)$で処理できるが、メモリを$O(N\log U)$消費する。Y-fast Trieは「集合全体を管理するのではなく、$O(\log U)$個おきの代表元だけをX-fast Trieに乗せ、残りは代表元ごとの小さな構造に分散させる」ことでメモリを$O(N)$に削減する。
ヒント2: アプローチ
値域を幅$\Theta(\log U)$の連続したバケットに分割し、各バケットの代表元だけを疎な集合として管理する。挿入・削除はまず$x$がどのバケットに属するかを特定し、そのバケット内部の小さな集合に対して操作を行う。
ヒント3: 誘導（コード骨格） 
import bisect

BUCKET_BITS = 10          # バケット幅 = 2^10 = 1024
representatives = []      # バケット代表元(id)のソート済みリスト
buckets = {}               # bucket_id -> ソート済みリスト

模範解答 (Python)

import sys
import bisect


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    Q = int(data[idx]); idx += 1

    BUCKET_BITS = 10

    buckets = {}
    rep_list = []

    def bucket_id(x):
        return x >> BUCKET_BITS

    def insert(x):
        bid = bucket_id(x)
        if bid not in buckets:
            buckets[bid] = []
            bisect.insort(rep_list, bid)
        lst = buckets[bid]
        pos = bisect.bisect_left(lst, x)
        if pos == len(lst) or lst[pos] != x:
            lst.insert(pos, x)

    def delete(x):
        bid = bucket_id(x)
        if bid not in buckets:
            return
        lst = buckets[bid]
        pos = bisect.bisect_left(lst, x)
        if pos < len(lst) and lst[pos] == x:
            lst.pop(pos)
            if not lst:
                del buckets[bid]
                rp = bisect.bisect_left(rep_list, bid)
                rep_list.pop(rp)

    def successor(x):
        bid = bucket_id(x)
        if bid in buckets:
            lst = buckets[bid]
            pos = bisect.bisect_right(lst, x)
            if pos < len(lst):
                return lst[pos]
        rp = bisect.bisect_right(rep_list, bid)
        if rp < len(rep_list):
            nb = rep_list[rp]
            return buckets[nb][0]
        return -1

    def predecessor(x):
        bid = bucket_id(x)
        if bid in buckets:
            lst = buckets[bid]
            pos = bisect.bisect_left(lst, x)
            if pos > 0:
                return lst[pos - 1]
        rp = bisect.bisect_left(rep_list, bid)
        if rp > 0:
            pb = rep_list[rp - 1]
            return buckets[pb][-1]
        return -1

    out = []
    for _ in range(Q):
        t = data[idx]; idx += 1
        x = int(data[idx]); idx += 1
        if t == b'I':
            insert(x)
        elif t == b'D':
            delete(x)
        elif t == b'S':
            out.append(str(successor(x)))
        else:
            out.append(str(predecessor(x)))
    print('\n'.join(out))


solve()
計算量: 本解答はバケット幅を固定した簡略版であり、各操作はバケット内の`bisect`挿入(最悪O(bucket size))に依存する。真のY-fast Trieでは代表元側をハッシュベースのX-fast Trieに、バケット側を平衡二分探索木にすることで償却$O(\log\log U)$を達成する。入力例1・2の手計算シーケンスと突き合わせ、全出力が一致することを確認済み。

Step-by-Step 解説

1X-fast Trieの弱点
各レベルにハッシュテーブルを持たせるため挿入のたびに$O(\log U)$個のノードを生成し、メモリが$O(N\log U)$に膨らむ。
2バケット化による疎化
値域を$\Theta(\log U)$幅のバケットに分割し、各バケットの代表元だけを俯瞰する構造に登録することで全体のメモリを$O(N)$に抑える。
3successorクエリの2段階探索
まず$x$が属するバケット内を調べ、なければ次に空でないバケットを代表元リストから探す。
4バケットの生成・消滅管理
最初の要素が入るときに代表元リストへ登録し、最後の要素が消えるときに代表元リストから削除する。
5理論上の計算量との対応
真のY-fast Trieでは代表元側をX-fast Trie、バケット側を平衡二分探索木で持たせ、全操作を償却$O(\log\log U)$にできる。

よくあるミス

ミス原因正しい書き方
バケットが空になったのに代表元リストから消し忘れるバケット内の要素だけ消して満足してしまうバケットが空になったらdel buckets[bid]しrep_listからも削除する
successorで同じバケット内の探索を怠り次バケットへ進むバケット構造を単なる目印としか思っていないまず現在のバケット内でbisect_rightにより候補を探す
バケット幅を大きくしすぎて1バケットに集中するBUCKET_BITSの意味を軽視するNの見積もりに応じてBUCKET_BITSを調整する
存在しない要素をDELETEしようとしてエラーになる削除は必ず成功するという前提でコードを書くbisect_leftで見つかった場合のみpopする

次のステップ

  • 発展: 代表元側を真のX-fast Trieに置き換え、バケット側を平衡二分探索木にして理論通りの償却$O(\log\log U)$を達成する。
  • 次回予告: Stable Roommates Problem（安定ルームメイト問題・Irvingのアルゴリズム）

自己評価

自分の回答

気づき・メモ