Chapter 12: Advanced Data Structures

When the whole edge list is known, set count = $n$ and call union(u, v) for each edge. A union succeeds when find(u) and find(v) differ; then the two components merge and count drops by one. When the roots already match, the edge is redundant: u and v were already connected, so the edge closes a cycle. After all edges, count is the number of components, which also equals the number of $x$ with find(x) = x. Each edge costs $O(\alpha(n))$, so the total is practically linear. Recording the failed unions turns the same loop into a cycle detector, the test behind Graph Valid Tree.

In the online setting, edges arrive one at a time and connectivity queries are interleaved with them: are u and v connected right now? Rerunning BFS after each edge costs $O(V + E)$ per query. Union Find answers each query with two finds, comparing roots in $O(\alpha(n))$, and each new edge is one union, with nothing rebuilt. The limitation is deletion. A union cannot be undone, because the structure does not record which edge caused a merge. If deletions are known in advance, process the timeline backwards so they become insertions. Fully dynamic connectivity needs heavier structures, such as Euler-tour trees, at polylogarithmic cost per operation.

Each node holds two things: a map from a character to the child node reached by that character, and a boolean is_end that is true when the path to this node spells a complete stored word. The root is empty and stands for the empty prefix. The child map can be a fixed array of 26 slots for lowercase letters, which is fast to index but wastes memory when most slots are empty, or a dictionary, which stores only the children that exist. Shared prefixes are stored once, so a trie of $N$ words of total length $T$ has at most $T + 1$ nodes, and far fewer when many words share beginnings.

All three operations walk from the root one character at a time. insert creates any missing child along the way and sets is_end on the last node. search follows the same path, returns False as soon as a character has no child, and at the end returns the node's is_end flag. startsWith is identical except that it returns True whenever the whole path exists, since a prefix need not be a stored word. Each step is one dictionary lookup, so all three run in $O(L)$ for a string of length $L$. A common bug is letting search return True whenever the path exists, which reports every prefix as a word.

Autocomplete has two phases. First walk from the root along the prefix's characters; if any character is missing, no stored word has this prefix, so return an empty list at once. Otherwise the walk ends at the prefix node, and every matching word lies in its subtree. Second, run a depth-first search from that node, carrying the string built so far: append a character when descending, drop it when returning, and emit the string at every node flagged is_end. Visiting children in sorted order yields alphabetical completions. The cost is the prefix walk plus the subtree size, independent of how many unrelated words the dictionary holds.

Users want a few good suggestions, not every match. Store a frequency at each word-end node. The simple method collects all matches and sorts them by frequency, costing $O(M \log M)$ for $M$ matches. Better, keep a min-heap of size $k$ during the DFS: push each match, and when the heap exceeds $k$, pop the least frequent, for $O(M \log k)$ total. The heap is not in ranked order, so sort its $k$ items at the end. For interactive speed, precompute each node's top-$k$ list; lookup is then $O(|p| + k)$, but an insertion must update the list at every ancestor. Break frequency ties by word so results are deterministic.

Python's collections.OrderedDict is a hash map that also remembers the order of its keys, backed internally by a doubly linked list. Two methods are all an LRU cache needs, both $O(1)$: move_to_end(key) marks a key as most recently used, and popitem(last=False) removes the key at the front, the least recently used. On get, return -1 for a missing key; otherwise move it to the end and return its value. On put, store the value, move the key to the end, and if the size exceeds capacity, pop from the front. The frequent bug is forgetting move_to_end on get, which silently turns LRU into first-in, first-out eviction.

Without an ordered map, build both parts yourself. Each list node stores a key, a value, and prev and next pointers; the hash map sends each key to its node. Sentinel head and tail nodes bracket the list, so no operation has to handle an empty list. The node after head is least recently used; the node before tail is most recent. On get, look up the node, unlink it, and re-insert it before tail. On put, update or create the node and move it before tail; if over capacity, unlink the node after head and delete its key. Every step is a constant number of pointer changes.

Store the tree in a flat array with no pointers: the root is index 1, and node $i$ has children $2i$ and $2i + 1$. Node $i$ covers a range $[l, r]$; its left child covers $[l, m]$ and its right child $[m+1, r]$, where $m = \lfloor (l + r)/2 \rfloor$. To build, recurse to the leaves, copy each array value into its leaf, and on the way back set tree[i] = tree[2i] + tree[2i+1], or min or max for other aggregates. There are $2n - 1$ nodes and each is computed once, so building is $O(n)$. When $n$ is not a power of two, indices can exceed $2n$, so allocate $4n$ entries.

A range query for $[q_l, q_r]$ starts at the root and compares each node's range with the query. If the node's range lies entirely inside, return its stored value. If it lies entirely outside, return the identity, 0 for sums or infinity for minima. Otherwise recurse into both children and combine. At most four nodes per level are visited, so a query is $O(\log n)$. A point update at index $i$ descends to the leaf for $i$, replaces its value, and recomputes each ancestor from its children on the way back, one node per level. Updating a whole range this way costs $O(n)$; lazy propagation reduces it to $O(\log n)$.