Advanced Structures

The specialists at a glance

Tries: prefix trees

A trie (from retrieval, usually pronounced "try") stores strings character by character along paths from the root. Each node has a map from the next character to a child, plus a flag marking whether a word ends there. Words that share a prefix share the path for it. Looking up a word of length L takes L steps no matter how many words are stored, and finding everything with a given prefix is a walk to the prefix's node followed by a traversal of its subtree.

A dict or set answers "is this exact word present?" just as fast, but cannot answer "which words start with car?" without scanning every key. That is why tries power autocomplete, spell checkers, IP routing tables (longest-prefix match on bits), and T9-style keyboards.

What to remember: O(L) per operation regardless of n; prefix queries are the reason to use one. You will build a scored trie in Project 3.

Union-find (disjoint set union)

Union-find maintains a partition of n items into disjoint groups and supports two operations: union(a, b) merges the groups containing a and b, and find(a) returns a representative (the root) of a's group. Two items are connected exactly when they have the same root. Each group is stored as a tree of parent pointers in a single list: parent[i] is i's parent, and a root is its own parent.

Naively, trees can become long chains and find is O(n). Two small tricks fix this:

• Union by rank (or by size): attach the shorter tree under the taller one, so heights grow only when two equal-height trees merge. Alone, this keeps height O(log n).
• Path compression: during find, point every node on the path directly at the root. The next find on any of them is one step.

Together they give an amortized cost of O(α(n)) per operation, where α is the inverse Ackermann function. The Ackermann function grows so absurdly fast that α(n) ≤ 4 for any n that could fit in the observable universe. In practice, union-find is constant time; theoretically, it is the slowest-growing non-constant bound you will ever meet (and Tarjan proved you cannot do better).

Where it is used

• Dynamic connectivity: edges arrive over time ("these two accounts share a phone number") and you need to answer "same group?" instantly. BFS would rerun on every query; union-find just merges.
• Kruskal's minimum spanning tree (M31): sort edges by weight and add each one unless find(u) == find(v), which would close a cycle.
• Cycle detection in undirected graphs, image segmentation (connected pixel regions), percolation simulations, and equivalence of type variables in compilers.

Fenwick trees: prefix sums with updates

Suppose you track sales per day and must answer "total sales from day l to day r" while sales keep being corrected. A plain prefix-sum array (from M30) answers range sums in O(1) but needs O(n) to rebuild after each update; the raw array updates in O(1) but sums in O(n). A Fenwick tree (binary indexed tree, 1994) does both in O(log n) with a single list and about ten lines of code.

The trick is the lowbit: i & -i isolates the lowest set bit of i (two's complement makes -i flip every bit above it). With 1-based indexes, slot tree[i] stores the sum of the lowbit(i) elements ending at i. So tree[8] holds elements 1..8, tree[6] holds 5..6, and tree[7] holds just 7.

Segment trees: any associative range query

A segment tree is a complete binary tree over the array: each leaf is one element, and each internal node stores the combination (sum, min, max, …) of its two children's ranges. The root covers the whole array. A query for [l, r) combines O(log n) nodes whose ranges tile the query exactly; a point update changes one leaf and its O(log n) ancestors. The combining operation only needs to be associative with an identity (0 for sum, ∞ for min), so the same code handles many problems.

Bloom filters: probably yes, definitely no

A Bloom filter answers set membership using a fraction of the memory of a set, at the price of occasional false positives. It is an array of m bits, all 0, plus k independent hash functions. To add an item, set the k bits it hashes to. To query, check those k bits: if any is 0, the item was definitely never added; if all are 1, it was probably added (or other items happened to set all k bits). There are never false negatives, and items cannot be removed (clearing a bit might erase other items).

After inserting n items, the probability that a particular bit is still 0 is (1 − 1/m)^kn ≈ e^−kn/m. A false positive needs all k probed bits to be 1, so

false_positive_rate ≈ (1 - e^(-k*n/m)) ** k
best k = (m / n) * ln 2          # about 0.7 * bits per item
bits per item for rate p: m/n = -ln(p) / (ln 2)^2  ≈ 9.6 bits for 1%, 14.4 bits for 0.1%

About ten bits per item for a 1% error rate, whatever the items are: a 100-byte URL costs 1.2 bytes. Browsers have used Bloom filters to screen URLs against malware lists, databases such as Cassandra and RocksDB use them to skip disk reads for keys that are not in a file, and CDNs use them to avoid caching one-hit wonders.

LRU caches

A cache keeps a limited number of expensive results. When it is full, which entry should go? Least recently used (LRU) evicts the entry that has gone unused longest, betting that recent use predicts future use (temporal locality). It is the default policy for CPU caches, page caches, CDN edges, and functools.lru_cache.

An LRU cache needs O(1) lookup by key and O(1) "move to most recent" and "remove least recent". No single structure does both, so combine two: a dict from key to node, and a doubly linked list (M21) ordered by recency. The dict finds the node; the list unlinks and relinks it in O(1) because each node knows both neighbors.

For caching function results, the standard library already has it. @functools.lru_cache(maxsize=...) memoizes calls keyed by their arguments (which must be hashable), and @functools.cache is the unbounded version. cache_info() reports hits and misses; cache_clear() empties it.

Skip lists, and sorted containers in Python

A skip list is a sorted linked list with express lanes. Every node is in level 0; each node is also promoted to level 1 with probability ½, to level 2 with probability ¼, and so on. A search starts in the top lane, runs right while the next key is smaller, and drops down a level when it would overshoot. Expected cost is O(log n) for search, insert, and delete, the same as a balanced tree, with no rotations: randomness does the balancing. Redis uses skip lists for sorted sets, and they are popular in concurrent code because inserts touch only local pointers.

Python's standard library has no skip list or balanced tree. The usual answer is the pure-Python sortedcontainers package (pixi add sortedcontainers): SortedList, SortedDict, and SortedSet keep values in a list of sorted sublists, which turns out to be faster than trees in Python because it works with bisect and CPU caches rather than against them.

Pitfalls

• Trie memory. Node-per-character tries are big in Python. Compress them or use a sorted list with bisect for prefix ranges if memory matters.
• Union-find without both optimizations degrades on adversarial input; at least use one, ideally both. Also, union-find cannot split groups; deletions need other structures.
• Off-by-one in Fenwick trees. They are 1-based; index 0 would loop forever because 0 & -0 == 0. Convert at the API boundary.
• Bloom filters lie in one direction. "Probably present" still needs a real lookup if a false positive matters. Size them for the final n; overfilling makes the FP rate climb fast.
• Unhashable or mutable cache keys. lru_cache raises TypeError for list arguments; convert to tuples. Never mutate a returned cached object, since every caller shares it.
• Building it when a library exists. In production prefer functools.lru_cache, sortedcontainers, and well-tested packages; build these yourself to understand them and for interviews.

Practice

END = "$"

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node[END] = True

    def _node(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._node(word)
        return node is not None and END in node

    def starts_with(self, prefix):
        return self._node(prefix) is not None

    def with_prefix(self, prefix):
        node = self._node(prefix)
        out = []
        def walk(n, text):
            if END in n:
                out.append(text)
            for ch in sorted(k for k in n if k != END):
                walk(n[ch], text + ch)
        if node is not None:
            walk(node, prefix)
        return out

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

class Fenwick:
    def __init__(self, values):
        n = len(values)
        self.tree = [0] + list(values)
        for i in range(1, n + 1):
            j = i + (i & -i)
            if j <= n:
                self.tree[j] += self.tree[i]

    def add(self, i, delta):
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

    def __len__(self):
        return len(self.data)

import hashlib
import math

def optimal_params(n, p):
    m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
    k = max(1, round(m / n * math.log(2)))
    return m, k

class BloomFilter:
    def __init__(self, n, p):
        self.m, self.k = optimal_params(n, p)
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        d = hashlib.sha256(item.encode("utf-8")).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos // 8] |= 1 << (pos % 8)

    def __contains__(self, item):
        return all(self.bits[pos // 8] >> (pos % 8) & 1 for pos in self._positions(item))

class MinSegmentTree:
    def __init__(self, values):
        self.n = n = len(values)
        self.t = [float("inf")] * n + list(values)
        for i in range(n - 1, 0, -1):
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, value):
        i += self.n
        self.t[i] = value
        while i > 1:
            i //= 2
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):
        best = float("inf")
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                best = min(best, self.t[l])
                l += 1
            if r & 1:
                r -= 1
                best = min(best, self.t[r])
            l //= 2
            r //= 2
        return best

Mini-project: a rate limiter with a sliding-window log and LRU

pixi init ratelimit && cd ratelimit
pixi add python=3.14 pytest
pixi run python -m pytest -q

Quiz

Recap

• Tries answer prefix queries in O(L); they trade memory for that power.
• Union-find (rank + path compression) answers "same group?" in effectively constant time; it powers Kruskal and dynamic connectivity.
• Fenwick trees use i & -i for O(log n) prefix sums with updates; segment trees handle any associative range query.
• Bloom filters give "definitely not" or "probably yes" in about 10 bits per item at 1% error: (1 − e^−kn/m)^k.
• LRU caches combine a dict with a doubly linked list (or OrderedDict); functools.lru_cache caches function calls.
• Skip lists balance by randomness; in Python, sortedcontainers is the practical sorted collection.

Going further

• functools.lru_cache and collections.OrderedDict
• hashlib for stable hashes
• sortedcontainers
• Bloom filter (with the derivation of the error rate)
• Next: put it together in Project 3: Autocomplete Engine, then on to Part 4: Algorithms.