Advanced Data Structures I

import math

class VEB:
    """
    Van Emde Boas tree for universe {0, ..., u-1}.
    u must be a power of 4 (so sqrt(u) is an integer power of 2).
    All operations: O(log log u).
    """
    def __init__(self, u):
        self.u    = u
        self.min  = None          # not stored in cluster (key trick!)
        self.max  = None
        if u > 2:
            sq = int(math.isqrt(u))
            self.cluster = [VEB(sq) for _ in range(sq)]
            self.summary = VEB(sq)

    def _high(self, x): return x // int(math.isqrt(self.u))
    def _low(self, x):  return x %  int(math.isqrt(self.u))
    def _idx(self, i, j): return i * int(math.isqrt(self.u)) + j

    def insert(self, x):
        if self.min is None:          # empty structure
            self.min = self.max = x
            return
        if x < self.min:
            x, self.min = self.min, x  # swap: new x goes into cluster
        if self.u > 2:
            hi, lo = self._high(x), self._low(x)
            if self.cluster[hi].min is None:
                self.summary.insert(hi)      # first call: O(1) base case
            self.cluster[hi].insert(lo)      # second call (only one recurses!)
        if x > self.max:
            self.max = x

    def successor(self, x):
        if self.u == 2:
            return 1 if x == 0 and self.max == 1 else None
        if self.min is not None and x < self.min:
            return self.min
        hi, lo = self._high(x), self._low(x)
        # Look in same cluster first (one recursion)
        if self.cluster[hi].max is not None and lo < self.cluster[hi].max:
            j = self.cluster[hi].successor(lo)
            return self._idx(hi, j)
        # Else find next non-empty cluster (one recursion on summary)
        succ_hi = self.summary.successor(hi)
        if succ_hi is None:
            return None
        j = self.cluster[succ_hi].min
        return self._idx(succ_hi, j)

    def delete(self, x):
        if self.min == self.max:       # only one element
            self.min = self.max = None
            return
        if self.u == 2:
            self.min = self.max = (1 if x == 0 else 0)
            return
        if x == self.min:              # find new min (from smallest cluster)
            first_cluster = self.summary.min
            x = self._idx(first_cluster, self.cluster[first_cluster].min)
            self.min = x
        hi, lo = self._high(x), self._low(x)
        self.cluster[hi].delete(lo)    # first call
        if self.cluster[hi].min is None:
            self.summary.delete(hi)    # second call (only one recurses!)
            if x == self.max:
                sm = self.summary.max
                self.max = None if sm is None else self._idx(sm, self.cluster[sm].max)
        elif x == self.max:
            self.max = self._idx(hi, self.cluster[hi].max)

import random

class SkipNode:
    def __init__(self, key, level):
        self.key  = key
        self.next = [None] * (level + 1)   # forward pointers per level

class SkipList:
    """
    Randomised skip list. O(log n) expected time for all operations.
    With high probability O(log n) — probability 1 - O(1/n^c) for any c.
    """
    MAX_LEVEL = 16             # cap levels at log2(max_n)
    P         = 0.5            # promotion probability

    def __init__(self):
        self.head  = SkipNode(float('-inf'), self.MAX_LEVEL)
        self.level = 0         # current max level in use

    def _random_level(self):
        """Coin-flip promotion: geometric distribution, capped at MAX_LEVEL."""
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, key):
        """Returns True if key found. O(log n) expected."""
        cur = self.head
        for i in range(self.level, -1, -1):   # top level down
            while cur.next[i] and cur.next[i].key < key:
                cur = cur.next[i]              # go right
        cur = cur.next[0]                      # drop to level 0
        return cur is not None and cur.key == key

    def insert(self, key):
        """Insert key. O(log n) expected."""
        update = [None] * (self.MAX_LEVEL + 1)  # nodes that need updating
        cur = self.head
        # Find insertion position at each level
        for i in range(self.level, -1, -1):
            while cur.next[i] and cur.next[i].key < key:
                cur = cur.next[i]
            update[i] = cur

        new_level = self._random_level()
        if new_level > self.level:             # new levels needed
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.head
            self.level = new_level

        new_node = SkipNode(key, new_level)
        for i in range(new_level + 1):
            new_node.next[i] = update[i].next[i]
            update[i].next[i] = new_node

    def delete(self, key):
        """Delete key. O(log n) expected."""
        update = [None] * (self.MAX_LEVEL + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.next[i] and cur.next[i].key < key:
                cur = cur.next[i]
            update[i] = cur

        target = cur.next[0]
        if target and target.key == key:
            for i in range(self.level + 1):
                if update[i].next[i] != target:
                    break
                update[i].next[i] = target.next[i]
            # Shrink level if top levels now empty
            while self.level > 0 and self.head.next[self.level] is None:
                self.level -= 1

import random, math, collections

def simulate_skip_levels(n, trials=10_000):
    """
    Simulate level distribution for n-element skip list.
    Verify w.h.p. bound: max level <= c*log2(n) with high probability.
    """
    max_levels = []
    for _ in range(trials):
        # Generate level for each of n elements
        levels = []
        for _ in range(n):
            lvl = 0
            while random.random() < 0.5:
                lvl += 1
            levels.append(lvl)
        max_levels.append(max(levels))

    c_log_n = math.ceil(2 * math.log2(n))   # c=2 threshold
    exceeded = sum(1 for ml in max_levels if ml > c_log_n)
    print(f"n={n}: E[max level]={sum(max_levels)/trials:.2f}, "
          f"log2(n)={math.log2(n):.1f}, "
          f"P(max > 2*log2(n)) = {exceeded/trials:.4f}")
    # Should be very small (polynomial in 1/n)

# Check for n=100, 1000, 10000
for n in [100, 1000, 10000]:
    simulate_skip_levels(n)

def skip_list_successor(sl, key):
    """
    Successor query: smallest element > key. O(log n) expected.
    Uses same search path as regular search.
    """
    cur = sl.head
    for i in range(sl.level, -1, -1):
        while cur.next[i] and cur.next[i].key <= key:
            cur = cur.next[i]
    # cur.next[0] is now the first element > key
    return cur.next[0].key if cur.next[0] else None