# ── 1. Union-Find (Disjoint Set Union) ────────────────────────────────── class UnionFind: def __init__(self, n: int): self.parent = list(range(n)) self.rank = [0] * n self._count = n def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, a: int, b: int) -> None: ra, rb = self.find(a), self.find(b) if ra == rb: return if self.rank[ra] < self.rank[rb]: self.parent[ra] = rb elif self.rank[ra] > self.rank[rb]: self.parent[rb] = ra else: self.parent[rb] = ra self.rank[ra] += 1 self._count -= 1 def connected(self, a: int, b: int) -> bool: return self.find(a) == self.find(b) @property def count(self) -> int: return self._count # ── 2. Bloom Filter ───────────────────────────────────────────────────── import hashlib, struct class BloomFilter: def __init__(self, capacity: int = 100_000, fp_rate: float = 0.01): import math self._n = capacity self._m = int(-capacity * math.log(fp_rate) / (math.log(2) ** 2)) self._k = int((self._m / capacity) * math.log(2)) self._bits = bytearray((self._m + 7) // 8) def _hashes(self, item: str) -> list[int]: h = hashlib.sha256(item.encode()).digest() return [struct.unpack_from(" None: for pos in self._hashes(item): self._bits[pos >> 3] |= 1 << (pos & 7) def __contains__(self, item: str) -> bool: for pos in self._hashes(item): if not (self._bits[pos >> 3] & (1 << (pos & 7))): return False return True # ── 3. LRU Cache ──────────────────────────────────────────────────────── class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev: _Node | None = None self.next: _Node | None = None class LRUCache: def __init__(self, cap: int): self._cap = cap self._map: dict[int, _Node] = {} self._head = _Node() self._tail = _Node() self._head.next = self._tail self._tail.prev = self._head def _remove(self, node: _Node) -> None: node.prev.next = node.next node.next.prev = node.prev def _add_to_front(self, node: _Node) -> None: node.next = self._head.next node.prev = self._head self._head.next.prev = node self._head.next = node def get(self, key: int) -> int: node = self._map.get(key) if not node: return -1 self._remove(node) self._add_to_front(node) return node.val def put(self, key: int, val: int) -> None: if key in self._map: node = self._map[key] node.val = val self._remove(node) self._add_to_front(node) return if len(self._map) >= self._cap: lru = self._tail.prev self._remove(lru) del self._map[lru.key] node = _Node(key, val) self._add_to_front(node) self._map[key] = node # ── 4a. Segment Tree (range sum) ─────────────────────────────────────── class SegmentTree: def __init__(self, data: list[int]): self._n = len(data) self._tree = [0] * (4 * self._n) self._build(1, 0, self._n - 1, data) def _build(self, node: int, l: int, r: int, data: list[int]) -> None: if l == r: self._tree[node] = data[l] return mid = (l + r) >> 1 self._build(node * 2, l, mid, data) self._build(node * 2 + 1, mid + 1, r, data) self._tree[node] = self._tree[node * 2] + self._tree[node * 2 + 1] def query(self, ql: int, qr: int) -> int: return self._query(1, 0, self._n - 1, ql, qr) def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int: if ql <= l and r <= qr: return self._tree[node] if r < ql or l > qr: return 0 mid = (l + r) >> 1 return (self._query(node * 2, l, mid, ql, qr) + self._query(node * 2 + 1, mid + 1, r, ql, qr)) def update(self, idx: int, val: int) -> None: self._update(1, 0, self._n - 1, idx, val) def _update(self, node: int, l: int, r: int, idx: int, val: int) -> None: if l == r: self._tree[node] = val return mid = (l + r) >> 1 if idx <= mid: self._update(node * 2, l, mid, idx, val) else: self._update(node * 2 + 1, mid + 1, r, idx, val) self._tree[node] = self._tree[node * 2] + self._tree[node * 2 + 1] # ── 4b. Fenwick Tree (Binary Indexed Tree) ───────────────────────────── class FenwickTree: def __init__(self, n: int): self._n = n self._bit = [0] * (n + 1) def add(self, idx: int, delta: int) -> None: i = idx + 1 while i <= self._n: self._bit[i] += delta i += i & -i def prefix_sum(self, idx: int) -> int: i = idx + 1 total = 0 while i > 0: total += self._bit[i] i -= i & -i return total def range_sum(self, l: int, r: int) -> int: return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)