Day 133-Q1 | van Emde Boas Tree（整数順序集合のO(log log U)探索）

問題

整数の全順序集合 $S$（初期状態は空集合）を宇宙 $[0,U)$、$U=2^{20}$ 上で管理する。$Q$個のクエリを順に処理せよ。

1 x : $x$ を $S$ に追加（既に含まれるなら何もしない）
2 x : $x$ を $S$ から削除（含まれなければ何もしない）
3 x : $x$ より大きい最小の要素（successor）を出力、なければ -1
4 x : $x$ より小さい最大の要素（predecessor）を出力、なければ -1

入力形式

Q
type_1 x_1
...
type_Q x_Q

制約

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

$0 \le x_i < 2^{20}$

type は 1,2,3,4 のいずれか

入出力例

入力例1

出力例1

概念図

ヒント（段階的開示）

ヒント1（方向性）

$U$が大きくても、平衡木や`sortedcontainers`を使わずに$O(\log\log U)$で処理したい。ポイントは「宇宙を$\sqrt U$個のクラスタに分割し、各クラスタもまた宇宙$\sqrt U$の同じ構造として再帰的に扱う」という発想である。$x$を上位ビット（クラスタ番号`high(x)`）と下位ビット（クラスタ内位置`low(x)`）に分解することを考えよ。

ヒント2（アプローチ）

各ノードは「自分の最小値mn」「最大値mx」「クラスタ集合（辞書で疎に持つ）」「どのクラスタが空でないかを管理するsummary構造（宇宙√Uのvシ）」を持つ。最小値・最大値はそのノード自身にキャッシュする。挿入先のクラスタが空だったら、そのクラスタの中に再帰して入れる代わりに「mn=mx=x」とだけ設定して終わる、というトリックが最悪計算量をO(log log U)に抑える鍵。

ヒント3（誘導）

class VEB:
    __slots__ = ['u', 'mn', 'mx', 'summary', 'cluster', 'lowbits']
    def __init__(self, u):
        self.u = u
        self.mn = None
        self.mx = None
        self.summary = None      # 宇宙 sqrt(u) の VEB（遅延生成）
        self.cluster = {}        # {high(x): VEB}（遅延生成）
        k = u.bit_length() - 1   # u = 2^k
        self.lowbits = k // 2

    def high(self, x): return x >> self.lowbits
    def low(self, x):  return x & ((1 << self.lowbits) - 1)
    def index(self, h, l): return (h << self.lowbits) | l

模範解答 (Python)

import sys

class VEB:
    __slots__ = ['u', 'mn', 'mx', 'summary', 'cluster', 'lowbits']

    def __init__(self, u):
        self.u = u
        self.mn = None
        self.mx = None
        self.summary = None
        self.cluster = {}
        if u > 2:
            k = u.bit_length() - 1
            self.lowbits = k // 2
        else:
            self.lowbits = 0

    def high(self, x):
        return x >> self.lowbits

    def low(self, x):
        return x & ((1 << self.lowbits) - 1)

    def index(self, h, l):
        return (h << self.lowbits) | l

    def cluster_u(self):
        return 1 << self.lowbits

    def summary_u(self):
        k = self.u.bit_length() - 1
        return 1 << (k - self.lowbits)

    def member(self, x):
        if x == self.mn or x == self.mx:
            return True
        if self.u == 2:
            return False
        c = self.cluster.get(self.high(x))
        if c is None:
            return False
        return c.member(self.low(x))

    def _empty_insert(self, x):
        self.mn = x
        self.mx = x

    def insert(self, x):
        if self.member(x):
            return
        if self.mn is None:
            self._empty_insert(x)
            return
        if x < self.mn:
            x, self.mn = self.mn, x
        if self.u > 2:
            h, l = self.high(x), self.low(x)
            child = self.cluster.get(h)
            if child is None:
                child = VEB(self.cluster_u())
                self.cluster[h] = child
            if child.mn is None:
                if self.summary is None:
                    self.summary = VEB(self.summary_u())
                self.summary.insert(h)
                child._empty_insert(l)
            else:
                child.insert(l)
        if x > self.mx:
            self.mx = x

    def delete(self, x):
        if self.mn is None:
            return
        if self.mn == self.mx:
            if x == self.mn:
                self.mn = None
                self.mx = None
            return
        if self.u == 2:
            if x == 0:
                self.mn = 1
            else:
                self.mn = 0
            self.mx = self.mn
            return
        if x == self.mn:
            first_cluster = self.summary.mn if self.summary is not None else None
            if first_cluster is None:
                return
            x = self.index(first_cluster, self.cluster[first_cluster].mn)
            self.mn = x
        h, l = self.high(x), self.low(x)
        child = self.cluster.get(h)
        if child is None or child.mn is None:
            pass
        else:
            child.delete(l)
            if child.mn is None:
                del self.cluster[h]
                self.summary.delete(h)
                if x == self.mx:
                    summary_max = self.summary.mx if self.summary is not None else None
                    if summary_max is None:
                        self.mx = self.mn
                    else:
                        self.mx = self.index(summary_max, self.cluster[summary_max].mx)
            elif x == self.mx:
                self.mx = self.index(h, child.mx)

    def successor(self, x):
        if self.u == 2:
            if x == 0 and self.mx == 1:
                return 1
            return None
        if self.mn is not None and x < self.mn:
            return self.mn
        h, l = self.high(x), self.low(x)
        child = self.cluster.get(h)
        max_low = child.mx if child is not None else None
        if max_low is not None and l < max_low:
            offset = child.successor(l)
            return self.index(h, offset)
        succ_cluster = self.summary.successor(h) if self.summary is not None else None
        if succ_cluster is None:
            return None
        offset = self.cluster[succ_cluster].mn
        return self.index(succ_cluster, offset)

    def predecessor(self, x):
        if self.u == 2:
            if x == 1 and self.mn == 0:
                return 0
            return None
        if self.mx is not None and x > self.mx:
            return self.mx
        h, l = self.high(x), self.low(x)
        child = self.cluster.get(h)
        min_low = child.mn if child is not None else None
        if min_low is not None and l > min_low:
            offset = child.predecessor(l)
            return self.index(h, offset)
        pred_cluster = self.summary.predecessor(h) if self.summary is not None else None
        if pred_cluster is None:
            if self.mn is not None and x > self.mn:
                return self.mn
            return None
        offset = self.cluster[pred_cluster].mx
        return self.index(pred_cluster, offset)


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    q = int(data[idx]); idx += 1
    U = 1 << 20
    veb = VEB(U)
    out = []
    for _ in range(q):
        t = int(data[idx]); x = int(data[idx + 1]); idx += 2
        if t == 1:
            veb.insert(x)
        elif t == 2:
            veb.delete(x)
        elif t == 3:
            r = veb.successor(x)
            out.append(str(r) if r is not None else "-1")
        else:
            r = veb.predecessor(x)
            out.append(str(r) if r is not None else "-1")
    print("\n".join(out))

solve()

Step-by-Step 解説

1宇宙の再帰分割
$U=2^k$を上位$\lceil k/2\rceil$ビット（クラスタ番号）と下位$\lfloor k/2\rfloor$ビット（クラスタ内位置）に分割。各クラスタは宇宙$\sqrt U$の同じ構造として再帰定義。木の深さは$O(\log\log U)$段。

2mn/mxキャッシュと空クラスタ挿入トリック
挿入先クラスタが空なら`mn=mx=x`だけ設定して終わる。1回のinsertで実質1方向にしか再帰しないため$T(U)=T(\sqrt U)+O(1)=O(\log\log U)$。

3successor/predecessor
属するクラスタ内に大きい要素があれば再帰、なければsummaryで次の非空クラスタを探す。同じ理由で$O(\log\log U)$。

4deleteの4ケース
要素1個の消去／mnの付け替え／クラスタからの再帰削除／mxの更新、を慎重に場合分け。

5計算量とメモリ
全操作$O(\log\log U)$。辞書による遅延生成でメモリは$O(Q\log\log U)$に抑えられる。

よくあるミス

ミス	原因	正しい書き方
挿入時にクラスタが空でも通常どおり再帰	空クラスタ挿入トリックを忘れる	`child.mn is None`なら`_empty_insert`のみ呼びsummaryだけ更新
successor/predecessorでmn/mxのショートカットを省略	常にクラスタ・summaryに再帰し計算量悪化	`xself.mx`を最初にチェック
delete時にmnを消しても2番目の値へ更新し忘れ	mnはクラスタに実データとして格納されていない	summaryの最小クラスタから新しいmnを取り出し処理継続
既存要素を再insertすると構造が壊れる	教科書のvEB-INSERTはx∉Vが前提で重複挿入すると亡霊値が生まれる	insertの先頭で`if self.member(x): return`のガードを入れる

次のステップ

発展: `member(x)`クエリも同じ構造の副産物としてO(log log U)で答えられる。実装し動作確認せよ。
発展2: vEB木はY-fast Trieの元になったアイデア。メモリ効率とキャッシュ効率のトレードオフを比較整理せよ。
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 133-Q1 — van Emde Boas Tree（整数順序集合のO(log log U)探索）

問題