Day 133-Q2 — BB[α]木（重み平衡二分探索木・Size Balanced Tree）

2026-08-25 赤色 Master / Phase 8+ ★★★★★★★★★ サイズ比のみによる単一/二重回転 O(log N)

問題

空の集合から始め、$N$個の操作をオンラインに処理せよ。

  • 1 x : 相異なる整数 $x$ を集合に追加する（追加時点で $x$ は集合に存在しないことが保証される）
  • 2 k : その時点で集合に入っている要素のうち、$k$番目に小さい要素を出力する

通常のAVL木・赤黒木を使わず、部分木のサイズだけを使った回転判定（BB[α]木 / Size Balanced Tree）で実装すること。

入力形式

N
op_1
...
op_N

制約

$1 \le N \le 2\times10^5$
$x$: $-10^9 \le x \le 10^9$、相異なる整数
`2 k`のkはクエリ時点の要素数以下

入出力例

入力例1

7
1 5
1 2
1 8
2 1
2 2
2 3
1 1

出力例1

2
5
8

概念図

不変量違反 → 単一回転（size(t.left.left) > size(t.right)） Before（違反） t (size7) L (size5) R (size1) LL (size3) LR (size1) size(LL)=3 > size(R)=1 ⇒ 右回転が必要 → After（rotate_right） L (新root) LL (size3) t (size4) LR R LがLの子だったtを引き取り、LRがtの左子に移る（Lの右子だったLRを付け替え） 不変量: すべてのノードで size(子) ≥ size(甥=反対側の子の孫)。違反時のみ回転しmaintainを再帰的に波及させる

ヒント（段階的開示）

ヒント1（方向性）

AVL木は左右部分木の高さの差で回転を決めるが、BB[α]木は部分木のサイズ（要素数）の比率だけで回転を決める。挿入のたびに根から通った経路上のノードで「自分の子の部分木サイズが、反対側の子の孫（甥）のサイズより小さくなっていないか」だけをチェックすればよい。

ヒント2（アプローチ）

ノード$t$について、`size(t.left) >= size(t.left.left)`、`size(t.left) >= size(t.left.right)`、`size(t.right) >= size(t.right.left)`、`size(t.right) >= size(t.right.right)`の4つがすべて成り立てば平衡とみなす。違反したら単一回転または二重回転（子を先に回してから自分を回転）を行い、回転後は左右の子を先に再帰的に`maintain`し、最後に自分自身も`maintain`する。

ヒント3（誘導） 
def sz(t): return t.size if t else 0

def rotate_right(t):
    l = t.left
    t.left = l.right
    l.right = t
    update(t); update(l)
    return l

def maintain(t):
    if t is None: return t
    if t.left and sz(t.left.left) > sz(t.right):
        t = rotate_right(t)
    elif t.left and sz(t.left.right) > sz(t.right):
        t.left = rotate_left(t.left)
        t = rotate_right(t)
    elif t.right and sz(t.right.right) > sz(t.left):
        t = rotate_left(t)
    elif t.right and sz(t.right.left) > sz(t.left):
        t.right = rotate_right(t.right)
        t = rotate_left(t)
    else:
        return t
    t.left = maintain(t.left)
    t.right = maintain(t.right)
    return maintain(t)

模範解答 (Python)

import sys
sys.setrecursionlimit(500000)

class Node:
    __slots__ = ['key', 'left', 'right', 'size']
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.size = 1


def sz(t):
    return t.size if t else 0


def update(t):
    t.size = sz(t.left) + sz(t.right) + 1


def rotate_right(t):
    l = t.left
    t.left = l.right
    l.right = t
    update(t)
    update(l)
    return l


def rotate_left(t):
    r = t.right
    t.right = r.left
    r.left = t
    update(t)
    update(r)
    return r


def maintain(t):
    if t is None:
        return t
    if t.left and sz(t.left.left) > sz(t.right):
        t = rotate_right(t)
    elif t.left and sz(t.left.right) > sz(t.right):
        t.left = rotate_left(t.left)
        t = rotate_right(t)
    elif t.right and sz(t.right.right) > sz(t.left):
        t = rotate_left(t)
    elif t.right and sz(t.right.left) > sz(t.left):
        t.right = rotate_right(t.right)
        t = rotate_left(t)
    else:
        return t
    t.left = maintain(t.left)
    t.right = maintain(t.right)
    t = maintain(t)
    return t


def insert(t, key):
    if t is None:
        return Node(key)
    if key < t.key:
        t.left = insert(t.left, key)
    else:
        t.right = insert(t.right, key)
    update(t)
    return maintain(t)


def kth(t, k):
    left_size = sz(t.left)
    if k == left_size + 1:
        return t.key
    elif k <= left_size:
        return kth(t.left, k)
    else:
        return kth(t.right, k - left_size - 1)


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    root = None
    out = []
    for _ in range(n):
        op = data[idx]; v = int(data[idx + 1]); idx += 2
        if op == b'1':
            root = insert(root, v)
        else:
            out.append(str(kth(root, v)))
    print("\n".join(out))

solve()

Step-by-Step 解説

1不変量の意味
「子の部分木サイズ≥反対側の孫（甥）の部分木サイズ」が全ノードで成り立つ木の高さは$O(\log N)$であることが証明できる。
2単一回転 vs 二重回転
`t.left.left`が大きすぎるなら単一の右回転。`t.left.right`が大きすぎるときは`t.left`を左回転してから`t`を右回転する二重回転が必要（AVL木のLL/LRケースと同構造）。
3再帰的maintain
回転後は子孫側で新たな不平衡が生まれうるため、`t.left`・`t.right`・`t`自身の順に再帰的に`maintain`を呼び直し局所回転の連鎖を波及させる。
4k番目探索
「左部分木のサイズ+1」が現在ノードの順位に一致することを利用し、左・自分・右のどちらに進むか決める。$O(\log N)$。
5計算量
挿入は経路長$O(\log N)$、各ノードで定数回の回転判定なので全体$O(\log N)$。k番目探索も同様。

よくあるミス

ミス原因正しい書き方
単一回転と二重回転の条件を取り違える「孫」がt.left.leftかt.left.rightかで対処が変わることを混同t.left.leftが大きい→右回転のみ、t.left.rightが大きい→左回転してから右回転
回転後にsizeの更新順序を間違える親を先に更新すると古い子のサイズを参照してしまう回転関数内で必ず新しい子→新しい親の順にupdateを呼ぶ
maintainを1回しか呼ばず子孫に波及させない回転の連鎖で子孫側が不平衡になるケースを見落とすmaintainの最後でt.left・t.right・tを再帰的にmaintainし直す
kthのインデックス境界を間違える「左部分木サイズ+1」が自分の順位であることを見落とすk==left_size+1なら自分、k<=left_sizeなら左、それ以外は右へk-left_size-1を渡す

次のステップ

  • 発展: `delete(t, key)`を実装せよ。後継ノードとswapした後、削除経路に沿って`maintain`を呼ぶ必要がある。
  • 発展2: BB[α]木は理論的には$\alpha\in(0,1-\frac1{\sqrt2}]$の範囲で任意の$\alpha$が使える（Blum & Mehlhorn, 1980）。不変量から高さの上界を導出してみよ。
  • 次回予告: 次回のテーマは今後のセッションで選定

自己評価

自分の回答

気づき・メモ