Day 107-Q1 | X-fast Trie（エックスファストトライ）

問題

整数の universe サイズを表す $K$（値は $0$ 以上 $2^K$ 未満の整数のみ）が与えられる。空の集合 $S$ に対して、$Q$ 個のクエリを順に処理せよ。

1 x: $S$ に $x$ を追加する（すでに存在する場合は何もしない）
2 x: $S$ の要素のうち $x$ 以上で最小のものを出力する（存在しなければ -1）
3 x: $S$ の要素のうち $x$ 以下で最大のものを出力する（存在しなければ -1）

クエリはオンラインで処理せよ。挿入は $O(\log U)$、2/3 クエリは $O(\log \log U)$（$U=2^K$）で処理できるアルゴリズムを実装せよ。

入力形式

K Q
query_1
...
query_Q

制約

$0 \le K \le 20$

$1 \le Q \le 2\times10^5$

$0 \le x < 2^K$

入出力例

入力例1

出力例1

5
3
-1
-1
-1

$5,3$を追加後、$4$以上最小は$5$。$3$を再追加しても変化なし。$3$以下最大は$3$。$6$以上最小は無く-1。$0$以下最大も無く-1。$20$追加後、$25$以上最小は無く-1。

概念図: レベルごとのハッシュと分岐点からの補正

ヒント（段階的開示）

ヒント1: 方向性

単純なbisectを使ったソート済みリストでは、挿入のたびに配列をずらす必要があり$O(N)$かかる。heapqは最小値取得は得意だが「$x$以上で最小」のような任意の値からのsuccessor/predecessorクエリには向かない。二分探索木を使えば$O(\log N)$にはなるが、この問題はuniverseのビット幅$K$に対して$O(\log\log U)=O(\log K)$というさらに速い理論限界を達成できる特殊な整数集合構造を要求している。

ヒント2: アプローチ

$x$を$K$ビットの2進数とみなし、根から葉までの2分木（トライ木）を考える。深さ$d$のノードは「$x$の上位$d$ビットのプレフィックス」に対応する。挿入された全要素のプレフィックスをレベルごとのハッシュ表（dict）に記録すれば、「プレフィックス$p$がトライ上に存在するか」を$O(1)$で判定できる。ある値$x$に対して「最長一致プレフィックスの深さ」を、深さ$0$〜$K$の範囲で二分探索すれば$O(\log K)$で求まる。この最長一致ノードが「$x$が本来たどるはずだった経路から外れた分岐点」であり、そこから反対側（実際に存在する側）の子のmin/maxを見れば、successor/predecessorの手がかりが得られる。挿入済み要素は昇順の双方向連結リストでつないでおき、その手がかりのnext/prevを辿ることで正確な答えに到達する。

ヒント3: 誘導（コード骨格）

def find_deepest(x):
    lo, hi, best = 0, K, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        prefix = x >> (K - mid) if mid > 0 else 0
        if mid == 0 or prefix in level[mid]:
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return best
# find_deepestで得た深さdのノードで、xが進むべき子が存在しない
# → 存在する側の部分木のmin/maxを使い、連結リストのnext/prevで真の答えへ補正する

模範解答 (Python)

import sys

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

    level = [dict() for _ in range(K + 1)]
    nxt = {}
    prv = {}
    HEAD, TAIL = -1, -2
    nxt[HEAD] = TAIL
    prv[TAIL] = HEAD
    present = set()

    def find_deepest(x):
        lo, hi, best = 0, K, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            prefix = x >> (K - mid) if mid > 0 else 0
            if mid == 0 or prefix in level[mid]:
                best = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return best

    def successor(x):
        if not present:
            return None
        if x in present:
            return x
        d = find_deepest(x)
        if d == K:
            return x
        prefix = x >> (K - d) if d > 0 else 0
        node = level[d][prefix]
        bit = (x >> (K - d - 1)) & 1
        if bit == 1:
            pred = node['maxL']
            nx = nxt.get(pred, TAIL)
            return None if nx == TAIL else nx
        else:
            return node['minR']

    def predecessor(x):
        if not present:
            return None
        if x in present:
            return x
        d = find_deepest(x)
        if d == K:
            return x
        prefix = x >> (K - d) if d > 0 else 0
        node = level[d][prefix]
        bit = (x >> (K - d - 1)) & 1
        if bit == 1:
            return node['maxL']
        else:
            succ = node['minR']
            pv = prv.get(succ, HEAD)
            return None if pv == HEAD else pv

    def insert(x):
        if x in present:
            return
        succ = successor(x)
        if succ is None:
            p = prv[TAIL]
            nxt[p] = x; prv[x] = p; nxt[x] = TAIL; prv[TAIL] = x
        else:
            p = prv[succ]
            nxt[p] = x; prv[x] = p; nxt[x] = succ; prv[succ] = x
        present.add(x)
        for d in range(0, K + 1):
            prefix = x >> (K - d) if d > 0 else 0
            node = level[d].get(prefix)
            if node is None:
                node = {'l': False, 'r': False, 'minL': None, 'maxL': None, 'minR': None, 'maxR': None}
                level[d][prefix] = node
            if d < K:
                bit = (x >> (K - d - 1)) & 1
                if bit == 0:
                    node['l'] = True
                    node['minL'] = x if node['minL'] is None else min(node['minL'], x)
                    node['maxL'] = x if node['maxL'] is None else max(node['maxL'], x)
                else:
                    node['r'] = True
                    node['minR'] = x if node['minR'] is None else min(node['minR'], x)
                    node['maxR'] = x if node['maxR'] is None else max(node['maxR'], x)

    out = []
    for _ in range(Q):
        t = data[idx]; idx += 1
        x = int(data[idx]); idx += 1
        if t == b'1':
            insert(x)
        elif t == b'2':
            r = successor(x)
            out.append(str(r) if r is not None else "-1")
        else:
            r = predecessor(x)
            out.append(str(r) if r is not None else "-1")
    print("\n".join(out))


solve()

計算量: 挿入 $O(\log U)$（全レベル更新）、successor/predecessor $O(\log\log U)$（レベル存在判定の二分探索）。ランダム200ケースでbrute-force集合シミュレーションと一致することを確認済み。

Step-by-Step 解説

1レベルごとのハッシュ表でトライを表現
ノードオブジェクトを作らず、level[d]という辞書で「深さdに存在するプレフィックス」だけを記録する。空間は$O(N\log U)$。

2最長一致プレフィックスの深さを二分探索
find_deepest(x)は深さ0〜Kの間で存在判定（ハッシュ参照$O(1)$）を境に二分探索し、全体$O(\log K)$で終える。

3分岐点からsuccessor/predecessorを導く
xが進むべき方向の子が無ければ、反対側の子は必ず存在する。そこに含まれる要素は全てxより大きい/小さいので、min/maxと連結リストのnext/prevで正確な答えに補正する。

4挿入は連結リスト位置の確定→全レベル更新の順
挿入前にsuccessorを呼んで位置を特定し、双方向連結リストにO(1)で挿入。その後、深さ0〜Kの全levelを更新する。

よくあるミス

ミス	原因	正しい書き方
集合が空のときにsuccessor/predecessorで例外	level[0]が空でもfind_deepestが深さ0を「存在する」とみなす	関数冒頭で`if not present: return None`を入れる
insert後に連結リストのnext/prevを張り忘れる	level情報だけ更新しsuccessor用の実要素リンクを忘れる	挿入前にsuccessor(x)で位置を求め、連結リストも同時更新する
深さK（葉）到達時の分岐がない	find_deepestがKを返す（x自身が既存）ケースの処理漏れ	`if d == K: return x`を明示的に書く
`x >> (K-d)`でd=0の境界を誤る	ルート（空プレフィックス）の扱いを見落とす	`d>0 else 0`でd=0を特別扱いする

次のステップ

発展: 削除（4 x）クエリを追加する（遅延削除＋定期的な全体再構築、または各ノードのmin/maxを再計算する必要があり実装が大きく難化する）
発展: バケット化してY-fast Trieに拡張する（代表元だけをX-fast Trieで管理し、各バケットを平衡二分探索木にすることで$O(N)$空間に削減できる）
次回予告: Directed Steiner Tree（有向シュタイナー木・端末部分集合DP + 逆辺Dijkstra緩和）

自己評価

完全理解おおむね理解要復習

Day 107-Q1 — X-fast Trie（エックスファストトライ）

問題