Day 080-Q1 — van Emde Boas Tree（整数集合の全操作 $O(\log \log U)$）

問題

整数 $0 \le x < U$ を要素とする動的集合 $S$ に対して、以下の操作を高速処理せよ。

• insert x: $x$ を $S$ に追加
• delete x: $x$ を $S$ から削除（$x \notin S$ のとき無視）
• find x: $x \in S$ かどうか答える（Yes/No）
• successor x: $S$ の中で $x$ より大きい最小要素を答える（なければ -1）
• predecessor x: $S$ の中で $x$ より小さい最大要素を答える（なければ -1）

$U = 2^{20}$（宇宙サイズ）とし、クエリ数 $Q$ が最大 $5 \times 10^5$ あっても高速に応答すること。

入出力例

1048576 8
insert 5
insert 15
insert 3
find 5
find 7
successor 5
predecessor 10
delete 5

Yes
No
15
5

概念図: vEB Tree の再帰構造

ヒント

class vEB:
    def __init__(self, u):
        self.u = u
        if u <= 2:
            self.min = self.max = None
            return
        self.sqrt_u = 1 << ((u.bit_length() - 1 + 1) // 2)
        self.min = self.max = None
        self.summary = vEB(self.sqrt_u)
        self.clusters = [vEB(self.sqrt_u) for _ in range(self.sqrt_u)]

    def high(self, x): return x // self.sqrt_u
    def low(self, x):  return x % self.sqrt_u
    def index(self, h, l): return h * self.sqrt_u + l

模範解答

import sys
input = sys.stdin.readline

class vEB:
    """van Emde Boas Tree — O(log log U) per operation"""

    def __init__(self, u: int):
        self.u = u
        self.min_val = None
        self.max_val = None
        if u <= 2:
            self.sqrt_u = 0
            self.summary = None
            self.clusters = []
        else:
            bits = (u - 1).bit_length()
            half = (bits + 1) // 2
            self.sqrt_u = 1 << half
            self.summary = vEB(self.sqrt_u)
            self.clusters = [vEB(self.sqrt_u) for _ in range(self.sqrt_u)]

    def high(self, x): return x // self.sqrt_u
    def low(self, x):  return x % self.sqrt_u
    def idx(self, h, l): return h * self.sqrt_u + l

    def insert(self, x):
        if self.min_val is None:
            self.min_val = self.max_val = x
            return
        if x < self.min_val:
            x, self.min_val = self.min_val, x
        if x > self.max_val:
            self.max_val = x
        if self.u > 2:
            h, l = self.high(x), self.low(x)
            if self.clusters[h].min_val is None:
                self.summary.insert(h)
            self.clusters[h].insert(l)

    def delete(self, x):
        if self.min_val == self.max_val == x:
            self.min_val = self.max_val = None
            return
        if self.u == 2:
            self.min_val = self.max_val = 1 - x
            return
        if x == self.min_val:
            first_cluster = self.summary.min_val
            x = self.idx(first_cluster, self.clusters[first_cluster].min_val)
            self.min_val = x
        h, l = self.high(x), self.low(x)
        self.clusters[h].delete(l)
        if self.clusters[h].min_val is None:
            self.summary.delete(h)
        if x == self.max_val:
            sm = self.summary.max_val
            if sm is None:
                self.max_val = self.min_val
            else:
                self.max_val = self.idx(sm, self.clusters[sm].max_val)

    def find(self, x):
        if x == self.min_val or x == self.max_val:
            return True
        if self.u == 2 or self.min_val is None:
            return False
        return self.clusters[self.high(x)].find(self.low(x))

    def successor(self, x):
        if self.u == 2:
            if x == 0 and self.max_val == 1: return 1
            return None
        if self.min_val is not None and x < self.min_val:
            return self.min_val
        h, l = self.high(x), self.low(x)
        max_low = self.clusters[h].max_val
        if max_low is not None and l < max_low:
            return self.idx(h, self.clusters[h].successor(l))
        succ_cluster = self.summary.successor(h)
        if succ_cluster is None: return None
        return self.idx(succ_cluster, self.clusters[succ_cluster].min_val)

    def predecessor(self, x):
        if self.u == 2:
            if x == 1 and self.min_val == 0: return 0
            return None
        if self.max_val is not None and x > self.max_val:
            return self.max_val
        h, l = self.high(x), self.low(x)
        min_low = self.clusters[h].min_val
        if min_low is not None and l > min_low:
            return self.idx(h, self.clusters[h].predecessor(l))
        pred_cluster = self.summary.predecessor(h)
        if pred_cluster is None:
            if self.min_val is not None and x > self.min_val: return self.min_val
            return None
        return self.idx(pred_cluster, self.clusters[pred_cluster].max_val)


def main():
    U, Q = map(int, input().split())
    tree = vEB(U)
    out = []
    for _ in range(Q):
        parts = input().split()
        op, x = parts[0], int(parts[1])
        if op == 'insert':
            tree.insert(x)
        elif op == 'delete':
            tree.delete(x)
        elif op == 'find':
            out.append('Yes' if tree.find(x) else 'No')
        elif op == 'successor':
            r = tree.successor(x)
            out.append(str(r) if r is not None else '-1')
        elif op == 'predecessor':
            r = tree.predecessor(x)
            out.append(str(r) if r is not None else '-1')
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: 宇宙サイズの分割

$U$ を $\sqrt{U}$ ごとの cluster に分割。各要素 $x$ を high(x) = x // √U（cluster 番号）と low(x) = x % √U（cluster 内インデックス）の二層で管理する。

Step 2: insert の再帰 — Lazy Min

新しい要素を挿入するとき、min に直接書き込んで旧 min を再帰的に押し込むのが鍵。各ノードは min と max のみ自身に保持し、内部は再帰的に委譲する。このため min は「宙に浮いた」状態で管理される。

Step 3: successor の仕組み

1. $x < \text{min}$ → min が答え
2. 同 cluster 内に後継があればそこへ降りる
3. なければ summary から次の非空 cluster を探し、その min を返す

Step 4: delete の最悪ケース対処

min を削除するとき「最初の要素が入っている cluster の min 値」に min を更新してから、その cluster の min を削除する（lazy な min 更新）。

Step 5: 計算量の証明

再帰のサイズが $U \to \sqrt{U} \to \cdots \to 2$ と変化するため深さは $\log_2 \log_2 U$。$U = 2^{20}$ のとき深さ ≦ 10。各操作 $O(\log \log U)$。

よくあるミス

次のステップ

• 発展問題: vEB Tree を使った Dijkstra の high-water mark 実装（$O((V + E) \log \log V)$）
• 代替構造: Fusion Tree ($O(\log N / \log \log N)$)、x-fast trie、y-fast trie との比較

自己評価