Day 141-Q4 | Skip List

問題

整数の多重集合に対して $Q$ 個のクエリを順に処理せよ。

ADD x: $x$を1個追加
DEL x: $x$を1個削除（存在保証あり）
COUNT x: $x$未満の要素の個数を出力
KTH k: 昇順で$k$番目（1-indexed）の要素を出力

これをSkip List（各要素の挿入時にコイン投げで「レベル」を確率的に決定し、複数段のリンクリストを重ねて探索を高速化するデータ構造）を用いて処理せよ。

Skip List の要点

各要素はレベル1（最下段）から始まり、確率$1/2$で1つ上のレベルにも自分自身を持つ、という試行を繰り返す
レベル$\ell$のリンクリストは、レベル$\ell$以上を持つ要素だけを昇順につないだもの
探索は最上段から始め、次のノードの値が探索対象を超えない限り右に進み、それ以上進めなければ1段下に降りる

注意: 出力されるCOUNT・KTHの結果はデータ構造の内部乱数に依存せず、多重集合としての意味論だけで一意に定まる。

入力形式

Q
query_1
:
query_Q

制約

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

$1 \le x \le 10^9$

入出力例

入力例1

10
ADD 5
ADD 3
ADD 8
ADD 3
COUNT 5
KTH 1
KTH 3
DEL 3
KTH 3
COUNT 8

出力例1

入力例2

9
ADD 10
ADD 20
ADD 10
ADD 5
KTH 2
COUNT 10
DEL 10
COUNT 10
KTH 3

出力例2

概念図

ヒント（段階的開示）

ヒント1（方向性）

平衡二分探索木は回転操作で高さのバランスを維持するが、Skip Listは「そもそも高さが揃った木を作ろうとせず、確率的に高い塔をランダムに配置する」ことで期待値としてバランスの取れた探索経路を実現する。レベル$\ell$に到達する確率が$(1/2)^{\ell-1}$なので、レベル数の期待値は$O(\log N)$に抑えられる。

ヒント2（アプローチ）

各ノードは「値」と「各レベルでの次ノードへのポインタ配列」を持つ。探索・挿入・削除は「現在のレベルで進めるだけ進み、進めなくなったら1段下がる」共通ロジックで実装できる。COUNT・KTHを効率よく求めるには、各ノードに「そのノードから次ノードまでに何個の要素があるか」というスパン（span）を追加で持たせる拡張（indexable skip list）が必要になる。

ヒント3（誘導）

import random
MAX_LEVEL = 20
P = 0.5

class Node:
    __slots__ = ("val", "forward", "span")
    def __init__(self, val, level):
        self.val = val
        self.forward = [None]*level
        self.span = [1]*level

def random_level():
    lvl = 1
    while random.random() < P and lvl < MAX_LEVEL:
        lvl += 1
    return lvl

# insert(x): update配列とrank配列を記録しながら各レベルを右に進める
# count_less(x): 各レベルで val < x の間だけ進み、spanを積算する
# kth(k): 各レベルでspanがk以下の間だけ進み、kから引いていく

出力に影響するのは「多重集合として何個未満か／何番目の値か」だけであり、レベル構成の乱数系列そのものは出力に一切現れない。

模範解答 (Python)

import sys
import random

random.seed(12345)
MAX_LEVEL = 20
P = 0.5

class Node:
    __slots__ = ("val", "forward", "span")
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * level
        self.span = [1] * level

class SkipList:
    def __init__(self):
        self.head = Node(None, MAX_LEVEL)
        self.level = 1
        self.size = 0

    def _random_level(self):
        lvl = 1
        while random.random() < P and lvl < MAX_LEVEL:
            lvl += 1
        return lvl

    def add(self, x):
        update = [self.head] * MAX_LEVEL
        rank = [0] * MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            rank[i] = rank[i + 1] if i + 1 < self.level else 0
            while cur.forward[i] is not None and cur.forward[i].val < x:
                rank[i] += cur.span[i]
                cur = cur.forward[i]
            update[i] = cur
        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
                rank[i] = 0
                self.head.span[i] = self.size + 1
            self.level = new_level
        node = Node(x, new_level)
        for i in range(new_level):
            node.forward[i] = update[i].forward[i]
            node.span[i] = update[i].span[i] - (rank[0] - rank[i])
            update[i].forward[i] = node
            update[i].span[i] = rank[0] - rank[i] + 1
        for i in range(new_level, self.level):
            update[i].span[i] += 1
        self.size += 1

    def delete(self, x):
        update = [self.head] * MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].val < x:
                cur = cur.forward[i]
            update[i] = cur
        target = update[0].forward[0]
        for i in range(self.level):
            if update[i].forward[i] is target:
                update[i].span[i] += target.span[i] - 1
                update[i].forward[i] = target.forward[i]
            else:
                update[i].span[i] -= 1
        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1
        self.size -= 1

    def count_less(self, x):
        cur = self.head
        rank = 0
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].val < x:
                rank += cur.span[i]
                cur = cur.forward[i]
        return rank

    def kth(self, k):
        cur = self.head
        remaining = k
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] is not None and cur.span[i] <= remaining:
                remaining -= cur.span[i]
                cur = cur.forward[i]
        return cur.val

def main():
    data = sys.stdin.buffer.read().split()
    ptr = 0
    q = int(data[ptr]); ptr += 1
    sl = SkipList()
    out = []
    for _ in range(q):
        cmd = data[ptr].decode(); ptr += 1
        x = int(data[ptr]); ptr += 1
        if cmd == "ADD":
            sl.add(x)
        elif cmd == "DEL":
            sl.delete(x)
        elif cmd == "COUNT":
            out.append(str(sl.count_less(x)))
        elif cmd == "KTH":
            out.append(str(sl.kth(x)))
    print('\n'.join(out))

main()

Step-by-Step 解説

1Skip List のレベル構造
各要素は最下段に必ず登録され、確率$1/2$で1つ上のレベルにも登録される試行を繰り返す。レベル$\ell$の要素数は期待値として全体の$(1/2)^{\ell-1}$倍になり、上位レベルほど疎な「飛び石」構造になる。

2スパン(span)による順位付きクエリの拡張
各リンクに「渡ると要素が何個進むか」というspanを持たせることで、探索中にspanを積算すれば「今何番目の要素にいるか」が分かる(indexable skip list)。

3なぜ乱数の実装詳細が出力に影響しないか
全ての操作は「多重集合として何個未満か」「何番目の値か」という集合としての意味論にのみ依存する。レベル構成は探索の効率にのみ影響し、答えの値そのものは変わらない。

4挿入・削除の連結リスト操作
挿入時は各レベルで「新ノードより手前で止まった最後のノード」を記録し繋ぎ変える。spanはこの繋ぎ変えの際に挿入・削除された1要素分だけ増減させる。

5計算量とTreapとの対比
期待計算量は挿入・削除・探索いずれも$O(\log N)$。最大レベル$L=20$程度に制限すれば$N\le2^{20}$まで実用上十分対応できる。

よくあるミス

ミス	原因	正しい書き方
`COUNT x`を「$x$以下」の個数と誤読	`<=`と`<`の境界条件の読み違い	本問の仕様は「$x$未満」なので`< x`の個数を使う
`KTH k`を0-indexedで処理してしまう	一般的な配列アクセスの癖	本問は1-indexedなので$k$番目に相当する要素を返す
`DEL x`で該当値を複数個削除してしまう	多重集合の「1個だけ削除」の意味を見落とす	該当する値のノードを1つだけ見つけて削除する
Skip Listのレベルを固定長にせず可変長配列で管理	実装の簡略化を優先しすぎる	`MAX_LEVEL`を決め打ちし各ノードは自分のレベル分だけ配列を持つ
spanの更新を怠りCOUNT/KTHの結果が食い違う	挿入・削除時にspanの整合性を保つ処理が複雑で漏れやすい	挿入時は新ノードが挟まるレベルのspanを分割、それ以外の影響レベルは±1更新

次のステップ

発展: 本問のSkipListに対し、bisect.insortを使った$O(N)$の素朴な実装を参照実装として用意し、ランダムなクエリ列で数百ケースの突き合わせテストを行い、出力が完全一致することを確認せよ。さらに$Q\le2\times10^5$の実行時間を計測し速度比較も行うこと。
発展2: Skip Listのレベルごとの要素数分布を実測し、理論値（幾何分布$(1/2)^{\ell-1}\times N$）とどの程度一致するかをヒストグラムで可視化せよ。

自己評価

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

Day 141-Q4 — Skip List（乱択平衡探索木による多重集合クエリ）

問題