Advanced data structures: amortization, persistence, and succinct representations

Why this subject matters now

The asymptotic hierarchy of data structures was largely settled between 1975 and 1990: van Emde Boas trees (1975), universal hashing (Carter and Wegman, 1979), splay trees and the amortized framework (Sleator and Tarjan, 1985), Fibonacci heaps (Fredman and Tarjan, 1987), and persistence via node copying (Driscoll, Sarnak, Sleator, and Tarjan, 1989) all appeared in that window, alongside Tarjan's inverse-Ackermann analysis of union-find (1975) and the FKS perfect-hashing construction (Fredman, Komlós, and Szemerédi, 1984). What has changed since is not the theory but the machine it runs on and the scale it runs at, and both have made the constant factors and the space overheads that the classical analysis suppresses into first-order concerns.

Three shifts are worth naming. The first is that memory, not instruction count, is the bottleneck, so the winning hash table today is not the one with the best worst-case probe bound but the one that keeps a lookup inside one or two cache lines: Google's Swiss tables and Meta's F14 both pack control bytes so a SIMD scan resolves a bucket in a single line, which is a data-structure decision the RAM model cannot see. The second is that datasets outgrew the machine, which revived the succinct and compressed structures: a rank/select bitvector in \(n + o(n)\) bits (Jacobson, 1989), a wavelet tree, a compressed suffix array, or a Roaring bitmap now sit under production search and genomics systems because the difference between \(n\) bits and \(2n\) bits is the difference between fitting in RAM and not. The third is that streaming and approximate membership went mainstream: Bloom filters, counting filters, and their descendants gate reads in every log-structured merge-tree database, a topic developed further on the mining massive datasets page, which owns the streaming and sketching model. A practitioner today is expected to know not just that these structures exist but why their bounds hold, because the choice between them is made on the exact terms the proofs expose: extra bits, cache misses, and the difference between worst-case and amortized.

Amortized analysis by the potential method

Amortized analysis bounds the average cost of an operation over a worst-case sequence, with no probability anywhere. It exists because many structures are cheap on almost every operation and expensive on a few, in a pattern where the expensive operations are provably rare, and a per-operation worst-case bound would be pessimistic to the point of uselessness. A push onto a dynamic array is \(O(1)\) except when it triggers a resize costing \(\Theta(n)\); a Fibonacci-heap decrease-key is \(O(1)\) except when a cascade of cuts fires; a union-find find is a single pointer read except when it walks and compresses a long path. In each case the expensive events pay for themselves by the cheap events they enable, and amortized analysis is the accounting that makes that precise.

Three methods and their equivalence

There are three standard techniques and they compute the same number. The aggregate method bounds the total cost \(T(m)\) of any sequence of \(m\) operations directly and reports the amortized cost as \(T(m)/m\). The accounting method assigns each operation a charge, the amortized cost, possibly different from its real cost; when the charge exceeds the real cost the surplus is stored as credit on the structure, and when the real cost exceeds the charge the deficit is paid from stored credit; the method is valid as long as the credit never goes negative. The potential method fixes a function \(\Phi\) mapping each state of the structure to a real number and defines the amortized cost of the \(i\)-th operation as

where \(c_i\) is the real cost and \(\Phi_i\) is the potential after operation \(i\). The three are not merely analogous; the potential method is the accounting method with the credit made into a global state function, and the aggregate method is what you get by summing. Summing the potential definition telescopes:

If the potential is chosen so that \(\Phi_m \ge \Phi_0\) for every reachable final state, and the standard convention \(\Phi_0 = 0\) with \(\Phi_i \ge 0\) guarantees this, then \( \sum_i c_i \le \sum_i \hat{c}_i \): the total real cost is bounded above by the total amortized cost. That is the whole content of the method. To prove a sequence costs \(O(m \cdot g)\), exhibit a nonnegative \(\Phi\) with \(\Phi_0 = 0\) and show \(\hat{c}_i = O(g)\) for every operation. The credit of the accounting method is exactly \(\Phi_i - \Phi_0\), the stored-up difference; the aggregate bound \(T(m) = \sum c_i \le \sum \hat c_i\) is the telescoped inequality. Choosing \(\Phi\) well is the only art, and a good \(\Phi\) is one that is large exactly in the states from which an expensive operation can be triggered, so that the expensive operation releases potential to pay its own bill.

Dynamic-array doubling

A dynamic array holds \(size\) elements in a block of \(capacity\) cells. A push writes one element; if \(size = capacity\) beforehand, it first allocates a block of \(2\,capacity\) cells and copies the \(size\) existing elements, at cost \(size\), then writes. Take the potential

Immediately after a resize the array is exactly half full, \(size = capacity/2\), so \(\Phi = 2(capacity/2) - capacity = 0\); as it fills toward \(size = capacity\), \(\Phi\) climbs to \(2\,capacity - capacity = capacity\), which is exactly the copy cost of the next resize. The potential stores up precisely what the resize will spend. A non-resizing push has real cost \(c_i = 1\); it increments \(size\) by one and leaves \(capacity\) fixed, so \(\Delta\Phi = +2\), giving

A resizing push starting from \(size = capacity = s\) has real cost \(c_i = s + 1\): copy \(s\) elements and write one. Afterward \(size = s+1\) and \(capacity = 2s\), so \(\Phi\) goes from \(2s - s = s\) to \(2(s+1) - 2s = 2\), a change of \(2 - s\), giving

Every push, cheap or expensive, has amortized cost exactly 3, so \(m\) pushes cost at most \(3m\): \(O(1)\) amortized. The aggregate view confirms it. Starting from capacity 1, resizes happen when \(size\) reaches \(1, 2, 4, \dots, 2^{k}\), copying \(1 + 2 + 4 + \cdots + 2^{k} \le 2 \cdot 2^{k} \le 2m\) elements over \(m\) pushes, plus \(m\) writes, for total \(< 3m\). For \(m = 17\) the copies are \(1+2+4+8+16 = 31\) and the writes are \(17\), total \(48\), amortized \(48/17 \approx 2.82 < 3\), matching the bound. The reason the growth factor must be a constant greater than one, not an additive increment, is visible here: growing by a fixed \(+c\) cells makes the copy costs \(0 + c + 2c + \cdots\) sum to \(\Theta(m^2)\), quadratic, because the potential can never get ahead of the copies. Shrinking needs a hysteresis gap for the same reason: halve capacity only when \(size\) drops to \(capacity/4\), not \(capacity/2\), or an alternating push-pop at the boundary forces a resize every operation.

The binary counter

A \(k\)-bit binary counter supports increment, which flips the trailing run of 1-bits to 0 and the next 0-bit to 1, at real cost equal to the number of bits flipped. The natural potential is

An increment that flips a trailing run of \(t\) ones costs \(c_i = t + 1\) (clear \(t\) ones, set one zero). It removes \(t\) ones and adds one, so \(\Delta\Phi = 1 - t\), giving

Every increment has amortized cost 2, so \(n\) increments from zero cost at most \(2n\): \(O(1)\) amortized per increment even though a single increment can flip all \(k\) bits. The aggregate method gives the same answer more explicitly. Over \(n\) increments bit 0 flips every time (\(n\) flips), bit 1 every second time (\(\lfloor n/2 \rfloor\)), bit \(j\) every \(2^j\)-th time, so the total is

For \(n = 16\) the exact count is \(16 + 8 + 4 + 2 + 1 = 31 < 32\), verified directly by counting the bits that change on each increment. Both the geometric-series structure and the potential argument are the same fact seen from two sides: the potential \(\Phi\) is the credit sitting on the set bits, each 1-bit carrying one unit that pays for the future flip that will clear it.

Balanced binary search trees

A binary search tree answers predecessor, successor, membership, insert, and delete in time proportional to its height, so the entire game is keeping the height \(O(\log n)\) under updates. Two classical disciplines do this by maintaining a local invariant that forces global balance, and both restore the invariant after an update using rotations, the constant-time pointer surgery that changes shape while preserving in-order key sequence.

Red-black trees and why the height is logarithmic

A red-black tree colors each node red or black subject to four invariants: the root is black; every leaf sentinel (the null pointers, treated as black nodes) is black; a red node has no red child, so red nodes never chain; and every root-to-leaf path passes through the same number of black nodes, a quantity called the black-height \(bh\). The height bound follows from these two structural facts. On any root-to-leaf path the black nodes number \(bh\) and, by the no-two-reds rule, the red nodes are at most \(bh\) (they alternate at worst), so the path has length at most \(2\,bh\); the longest path is therefore at most twice the shortest. To bound \(bh\) itself, observe that the subtree rooted at any node of black-height \(b\) contains at least \(2^{b} - 1\) internal nodes, proved by induction: a leaf has \(b = 0\) and \(2^0 - 1 = 0\) internal nodes, and a node's two children each have black-height at least \(b - 1\), so the subtree holds at least \(2(2^{b-1} - 1) + 1 = 2^{b} - 1\). Hence \(n \ge 2^{bh} - 1\), so \(bh \le \log_2(n + 1)\), and the height is at most \(2 \log_2(n + 1) = O(\log n)\). Insert and delete restore the invariants with \(O(1)\) rotations and \(O(\log n)\) recolorings, so every dictionary operation is \(O(\log n)\) worst case. The reason red-black trees, rather than the strictly shallower AVL trees, sit under most standard-library ordered maps is that the amortized number of structural changes per update is \(O(1)\): a red-black delete performs at most three rotations, which matters when the nodes carry augmentation that must be recomputed along the changed path.

AVL trees and the Fibonacci lower bound on size

An AVL tree enforces that at every node the heights of the two subtrees differ by at most one. This is a tighter invariant than red-black balance and yields a shallower tree, at the cost of more rotations on update. The height bound comes from asking the extremal question: what is the fewest nodes \(N(h)\) an AVL tree of height \(h\) can have? Such a minimal tree has a root whose two subtrees are themselves minimal AVL trees, and to make the root's height \(h\) while using as few nodes as possible, one subtree has height \(h-1\) and the other, allowed to differ by one, has height \(h-2\). Thus

Adding one to each side gives \(N(h) + 1 = (N(h-1)+1) + (N(h-2)+1)\), the Fibonacci recurrence, so \(N(h) + 1 = F_{h+3}\) where \(F\) is the Fibonacci sequence, and \(F_{k} \sim \varphi^{k}/\sqrt{5}\) with \(\varphi = (1+\sqrt5)/2\). Therefore \(n \ge N(h) = F_{h+3} - 1 \approx \varphi^{h+3}/\sqrt5\), which inverts to

An AVL tree is thus never more than about 44% taller than a perfectly balanced tree, and in practice much closer, which is why AVL trees win when lookups dominate and updates are rare: the shallower tree pays off on every search. The rotation to restore balance after an insert is a single or double rotation at the lowest unbalanced ancestor, decided by the sign pattern of the balance factors, and it restores the height the subtree had before the insert, so at most one rotation is ever needed on insert.

Splay trees and the access lemma

A splay tree keeps no balance information at all. After every access it moves the accessed node to the root by a sequence of double rotations called splaying, chosen by the zig-zig and zig-zag cases so that the tree stays roughly balanced in an amortized sense. Splaying node \(x\) up past its parent \(p\) and grandparent \(g\) uses the zig-zig case when \(x\) and \(p\) are both left children or both right children, and the zig-zag case otherwise; the zig-zig case rotates \(p\) then \(x\), and this asymmetric choice, rather than repeatedly rotating \(x\) alone, is exactly what produces the logarithmic amortized bound rather than a linear one on a path.

The analysis assigns each node a positive weight \(w(x)\), defines the subtree weight \(s(x) = \sum_{y \in \text{subtree}(x)} w(y)\), and the rank \(r(x) = \log_2 s(x)\). The potential is the sum of ranks, \(\Phi = \sum_x r(x)\). The core result is the access lemma: the amortized cost of splaying \(x\) to the root is at most

The proof charges each splay step. Write \(r\) and \(r'\) for ranks before and after a step. A zig-zig or zig-zag step's real cost is 2 rotations; the potential change is \(r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g)\), and because \(x\) ends where \(g\) began, \(r'(x) = r(g)\). A convexity argument on the logarithm, \(\log a + \log b \le 2\log\frac{a+b}{2}\), applied to the disjoint subtrees that end up under \(x\), bounds the amortized cost of each such step by \(3(r'(x) - r(x))\). The single zig step, used at most once at the top, contributes at most \(3(r'(x) - r(x)) + 1\). Summing telescopes over the splay path: all intermediate ranks cancel and only \(r_{\text{final}}(x) - r_{\text{initial}}(x)\) survives, and \(r_{\text{final}}(x) = r(\text{root})\), giving the lemma. Taking all weights equal to 1 makes \(s(\text{root}) = n\) and \(s(x) \ge 1\), so \(r(\text{root}) - r(x) \le \log_2 n\), and the amortized cost of any access is \(O(\log n)\). A splay tree therefore matches a balanced tree amortized, without storing a single balance bit.

The weights are a proof device that can be chosen after the fact, and different choices yield stronger theorems for free. Setting \(w(x)\) proportional to the access frequency \(f_x\) and summing the access lemma over a sequence gives the static optimality theorem: a splay tree serving a sequence in which item \(x\) is requested \(f_x\) times out of \(m\) total costs \(O\!\left(m + \sum_x f_x \log(m/f_x)\right)\), which is within a constant factor of the cost of the best static tree, the one an offline algorithm would build knowing the frequencies, whose cost is the entropy \(\sum_x f_x \log(m/f_x)\). The working-set theorem, from a time-varying weighting, shows the cost of accessing \(x\) is \(O(\log t)\) where \(t\) is the number of distinct items touched since \(x\) was last accessed, so recently and frequently used items are cheap, a self-adjusting cache property no static tree has. The open dynamic optimality conjecture of Sleator and Tarjan asserts the strongest possible statement, that splay trees are \(O(1)\)-competitive against the optimal offline binary-search-tree algorithm for every access sequence; it remains unproven, and the best known online BST, the Tango tree of Demaine, Harmon, Iacono, and Pătrașcu (2007), is only \(O(\log \log n)\)-competitive.

Fibonacci heaps

A priority queue for a shortest-path algorithm is called with a specific mix: many decrease-key operations, one per edge relaxation, and comparatively few extract-min operations, one per vertex. A binary heap charges \(O(\log n)\) for both, so Dijkstra costs \(O((V + E)\log V)\). The Fibonacci heap of Fredman and Tarjan makes decrease-key \(O(1)\) amortized while keeping extract-min \(O(\log n)\) amortized, which drops Dijkstra to \(O(E + V \log V)\), asymptotically optimal in the comparison model and better whenever the graph is denser than a tree. The algorithm design page uses exactly this bound when it discusses Dijkstra and Prim; here is where it comes from.

A Fibonacci heap is a forest of heap-ordered trees with a pointer to the minimum root. Insert adds a single-node tree and updates the min pointer, in \(O(1)\), doing no consolidation. Decrease-key cuts the node from its parent, making it a new root, and if the parent had already lost a child it cuts the parent too, cascading up; each cut also clears or sets a "mark" bit that records whether a node has lost a child since it last became a child. Extract-min removes the min root, promotes its children to roots, and then consolidates by repeatedly linking roots of equal degree until all root degrees are distinct, which is the only expensive step. The potential is

the number of trees plus twice the number of marked nodes. Decrease-key that performs \(c\) cascading cuts has real cost \(O(c)\); it creates \(c\) new trees, so \(t\) rises by \(c\), but it clears the mark on every cut node except possibly the topmost, so \(m\) falls by at least \(c - 1\). Thus \(\Delta\Phi \le c - 2(c - 1) = 2 - c\), and the amortized cost is \(O(c) + (2 - c) = O(1)\): the marks are a savings account that pays for the cuts, and the factor of 2 on marks is precisely what is needed so that the \(-2\) per cleared mark cancels the \(+1\) per new tree with a unit to spare.

Extract-min's consolidation does work proportional to the number of roots, which after promotion is \(t(H) + D(n)\) where \(D(n)\) is the maximum degree, but consolidation reduces the root count to at most \(D(n) + 1\), releasing \(\Delta\Phi \le D(n) + 1 - t(H)\) of potential, so the amortized cost is \(O(D(n))\). The bound is finished by proving \(D(n) = O(\log n)\), and this is where the Fibonacci numbers and the name come from. A node of degree \(k\) in a Fibonacci heap roots a subtree of size at least \(F_{k+2}\). The argument: consider the children of a degree-\(k\) node in the order they were linked; the \(i\)-th child had degree at least \(i - 2\) at link time, because linking requires equal degree and a marked node loses at most one child before being cut, so the marking rule guarantees each child has kept nearly all its own children. Letting \(S_k\) be the minimum subtree size of a degree-\(k\) node gives \(S_k \ge 2 + \sum_{i=2}^{k} S_{i-2}\), which solves to \(S_k \ge F_{k+2} \ge \varphi^{k}\). Hence \(n \ge \varphi^{D(n)}\), so \(D(n) \le \log_\varphi n = O(\log n)\), and extract-min is \(O(\log n)\) amortized. The mark bit is not decoration: without the cascading cut a node could lose arbitrarily many children and the subtree-size bound would fail, breaking the degree bound and with it the whole analysis.

Union-find and the inverse-Ackermann bound

The disjoint-set structure maintains a partition under two operations: find(x) returns a canonical representative of \(x\)'s set, and union(x, y) merges the two sets. It is the engine of Kruskal's minimum-spanning-tree algorithm and of every incremental-connectivity computation. Represented as a forest where each element points at a parent and each tree's root is the representative, both operations reduce to walking to a root, and the entire subject is making that walk short with two heuristics whose combination is far better than either alone.

Union by rank alone gives logarithmic height

Union by rank attaches the shorter tree under the taller one, using a rank field that upper-bounds a node's height. When two roots of equal rank are unioned, one becomes the child and the survivor's rank increments; when the ranks differ, the lower-rank root is attached under the higher and no rank changes. The key invariant is that a root of rank \(r\) is the root of a tree with at least \(2^{r}\) nodes, proved by induction: rank 0 is a singleton with \(2^0 = 1\) node, and a rank-\(r\) root is created only by unioning two rank-\((r-1)\) roots, each with at least \(2^{r-1}\) nodes, for a total of at least \(2^{r}\). Hence the maximum rank is at most \(\log_2 n\), the height never exceeds the rank, and every find is \(O(\log n)\) worst case, with no amortization needed. Ranks are only ever upper-bounds on height once path compression starts flattening trees, which is why the field is called rank and not height.

Path compression and the \(O(\log^* n)\) bound

Path compression makes every node on a find's search path point directly at the root, so the next find on any of them is a single step. Combined with union by rank it makes the amortized cost per operation astonishingly small. The full bound is \(O(\alpha(n))\) where \(\alpha\) is an inverse of the Ackermann function, but the cleaner \(O(\log^* n)\) bound captures the essential mechanism and is worth proving; here \(\log^* n\) is the iterated logarithm, the number of times \(\log_2\) must be applied to bring \(n\) to at most 1, a function that is at most 5 for every \(n\) below \(2^{65536}\).

Two facts about ranks survive path compression. First, ranks strictly increase along any parent chain at every instant, because a node's rank is fixed once it stops being a root and its parent's rank was strictly larger when the link was made and only grows. Second, the number of nodes of rank exactly \(r\) is at most \(n / 2^{r}\), because each such node once rooted a disjoint set of at least \(2^{r}\) nodes. Now partition the possible ranks \(\{0, 1, \dots, \lfloor \log_2 n \rfloor\}\) into groups, where a rank \(r\) belongs to group \(g = \log^*(r)\); the number of groups is \(O(\log^* n)\), and group \(g\) spans the ranks in an interval whose upper end is a tower of twos, so the ranks in group \(g\) number at most \(2^{r_g}\) where \(r_g\) is the smallest rank in the next group. Charge the cost of the pointer walks in a find in two accounts. A step from a node to its parent is charged to the find if the parent is in a strictly higher rank group, and there are at most \(O(\log^* n)\) group boundaries on any path, so this account totals \(O(m \log^* n)\) over \(m\) operations. Otherwise the step is charged to the node; but each time a node is charged this way, path compression re-points it at a strictly higher-ranked node in the same group, and a node can be re-pointed within its group only as many times as the group has ranks before its parent leaves the group, which the rank-count bound caps so that the total node-charge over all nodes is \(O(n \log^* n)\). Adding the accounts, \(m\) operations cost \(O((m + n)\log^* n)\), amortized \(O(\log^* n)\) each.

The tight analysis of Tarjan (1975) replaces the two-level grouping with an \(\alpha\)-level grouping and yields \(O(\alpha(n))\). The Ackermann function may be defined by \(A_0(x) = x + 1\) and \(A_{k+1}(x) = A_k^{(x+1)}(x)\), the \((x+1)\)-fold composition, so that \(A_1(x) = 2x + 1\), \(A_2(x)\) is exponential, \(A_3\) is a tower, and \(A_4\) already exceeds the number of atoms in the universe at \(x = 1\); the inverse \(\alpha(n) = \min\{k : A_k(1) \ge n\}\) is at most 4 for every \(n\) that can be written down. Fredman and Saks (1989) proved a matching \(\Omega(\alpha(n))\) lower bound in the cell-probe model, so the inverse-Ackermann cost is inherent, not an artifact of the analysis: no pointer-based disjoint-set structure can do better in the worst amortized case.

Range-query structures

A range query asks for an aggregate over a contigual band of an array, minimum, sum, or any associative reduction, possibly interleaved with point or range updates. The structures below trade preprocessing time, update support, and query time against one another, and each is built from a different piece of index arithmetic that is worth deriving rather than memorizing.

Sparse tables for idempotent queries

When the aggregate is idempotent, meaning combining a value with itself changes nothing, as with min, max, and gcd, a query can overlap two precomputed blocks without double-counting, and this buys \(O(1)\) queries after \(O(n \log n)\) preprocessing with no updates. Precompute \(\text{sp}[k][i] = \min\bigl(a[i], \dots, a[i + 2^{k} - 1]\bigr)\), the minimum of the block of length \(2^{k}\) starting at \(i\), by the doubling recurrence \(\text{sp}[k][i] = \min(\text{sp}[k-1][i],\ \text{sp}[k-1][i + 2^{k-1}])\), each level combining two half-blocks. To answer \(\min\) over \([l, r]\), let \(k = \lfloor \log_2 (r - l + 1) \rfloor\), the largest power of two that fits, and return \(\min(\text{sp}[k][l],\ \text{sp}[k][r - 2^{k} + 1])\). The two blocks each have length \(2^{k}\); the first starts at \(l\) and the second ends at \(r\), and because \(2^{k} \ge (r - l + 1)/2\) they overlap in the middle, covering \([l, r]\) with no gap. Idempotence is what makes the overlap harmless; for a sum, the overlap would be counted twice and the answer would be wrong, which is why sums need a segment tree or a Fenwick tree instead. The floor of the logarithm is precomputed in a table so the query has no floating-point step.

Segment trees

A segment tree stores an associative aggregate over every node of a balanced binary tree whose leaves are the array elements and whose internal nodes cover the union of their children's ranges. Laid out in an array with the root at index 1 and the children of \(i\) at \(2i\) and \(2i+1\), or in the iterative bottom-up layout with the \(n\) leaves at indices \(n\) to \(2n - 1\), it supports point update and range query each in \(O(\log n)\), and with lazy propagation it supports range update too. The query descends from the root, and at each node fully inside the query range it takes the stored aggregate whole, recursing only into nodes that straddle a range boundary; because a query range's two endpoints each cut at most one node per level, at most \(O(\log n)\) nodes are visited. The iterative form makes the decomposition explicit: to query \([l, r)\), set \(lo = l + n\) and \(hi = r + n\) at the leaf level and, while \(lo < hi\), take the node \(lo\) into the answer when \(lo\) is a right child (\(lo\) odd) and take \(hi - 1\) when \(hi\) is a right boundary (\(hi\) odd), then move both up a level with \(lo, hi \gets \lfloor lo/2\rfloor, \lfloor hi/2\rfloor\). The set of nodes taken is exactly the canonical \(O(\log n)\)-node cover of the interval.

Fenwick trees and the low-bit identity

A Fenwick tree, or binary indexed tree, supports prefix-sum query and point update each in \(O(\log n)\) using a single array and one line of index arithmetic per step, which is why it is the structure of choice when only sums and prefix sums are needed. The array \(t[1..n]\) is defined so that \(t[i]\) holds the sum of the array elements in the half-open range \((i - \text{lowbit}(i),\ i]\), where \(\text{lowbit}(i) = i \mathbin{\&} (-i)\) is the value of the lowest set bit of \(i\), the largest power of two dividing \(i\). This choice makes both operations a walk that clears or adds low bits. A prefix sum \(\sum_{j \le i} a[j]\) accumulates \(t[i]\), which covers a suffix ending at \(i\) of length \(\text{lowbit}(i)\), then jumps to \(i - \text{lowbit}(i)\) to cover the rest, repeating until the index reaches 0; each step strips the lowest set bit, so the number of steps is the number of set bits in \(i\), at most \(\log_2 n\). A point update at position \(i\) must adjust every \(t[j]\) whose range contains \(i\), which are the indices \(i, i + \text{lowbit}(i), i + \text{lowbit}(i) + \dots\), each adding its lowest bit and thereby moving to the next containing range, again \(O(\log n)\) steps. The two walks move in opposite directions along the bit structure, query stripping low bits and update adding them, which is the elegance of the structure: the same low-bit identity drives both, and the whole thing is a dozen lines with no tree pointers.

Lowest common ancestor by Euler tour and RMQ

The lowest common ancestor of two nodes in a rooted tree can be found in \(O(1)\) after linear preprocessing by reducing it to a range-minimum query, a reduction worth knowing because it turns a tree problem into an array problem the structures above already solve. Perform an Euler tour, a depth-first traversal that records each node every time it is entered, including on the way back up from a child, so the tour has length \(2n - 1\); alongside it record the depth of the node at each tour position and, for each node, the index of its first appearance. The lowest common ancestor of \(u\) and \(v\) is then the shallowest node encountered on the tour between the first appearances of \(u\) and \(v\): any walk from \(u\) to \(v\) in the tour must pass through their common ancestor and cannot go above it, so the minimum-depth entry in that tour range is exactly the LCA. This is a range-minimum query on the depth array, answerable in \(O(1)\) by a sparse table after \(O(n \log n)\) preprocessing, or in true \(O(n)\) preprocessing and \(O(1)\) query by the ±1 RMQ structure of Fischer and Heun (2006), which exploits that consecutive depths in an Euler tour differ by exactly one, so a block of the depth array is determined up to an additive constant by a bit pattern and small blocks can be tabulated exhaustively.

Persistence

A persistent data structure keeps its past. A partially persistent structure lets any past version be queried but only the newest version updated; a fully persistent structure lets any version, past or present, be updated to branch a new version, turning the version history from a line into a tree; a confluently persistent structure additionally allows two versions to be merged. Persistence is not a niche: it is how a functional language gives you an immutable map, how a database gives you a consistent snapshot for a long-running read, and how an editor gives you unlimited undo. The two general techniques trade space against simplicity.

The fat-node method stores, in each field of each node, the entire history of values that field has held, tagged by version number; a read at version \(v\) binary-searches the field's history for the latest value with version at most \(v\). This makes any pointer-based structure fully persistent with \(O(1)\) space per modification, but adds an \(O(\log m)\) factor to every field access from the binary search over \(m\) versions. The path-copying method instead copies every node on the path from the root to the modified node, leaving the old version's nodes untouched and sharing all the unchanged subtrees; the new version gets a new root, and the old root still names the old version. For a balanced tree the modified path has length \(O(\log n)\), so path copying costs \(O(\log n)\) time and \(O(\log n)\) new nodes per update, with no query slowdown at all, which is why it is the method used in practice for persistent search trees. The node-copying method of Driscoll, Sarnak, Sleator, and Tarjan (1989) improves the space to \(O(1)\) amortized per update while keeping \(O(1)\) query overhead, by giving each node a small number of extra modification slots and only copying when the slots fill, amortizing the copies with a potential argument on the number of full nodes.

The persistent segment tree is path copying applied to a segment tree, and it is the workhorse behind offline range queries such as the \(k\)-th smallest element in a subarray. Each point update creates \(O(\log n)\) new nodes along one root-to-leaf path and reuses the rest of the previous version, so \(m\) updates use \(O(m \log n)\) total space and every historical version is a valid segment tree reachable from its own stored root. To find the number of elements less than a threshold in a prefix, build one version per array prefix, each inserting the next element; the difference of two versions' aggregates over a value range answers a range-count query, because subtracting the version at the left endpoint from the version at the right endpoint isolates the elements in the subarray. As a worked instance, inserting the array \([3, 1, 2]\) into an initially empty count-segment-tree over values \(\{1, 2, 3\}\) produces versions \(V_0\) (empty), \(V_1\) (count of 3 is one), \(V_2\) (counts of 3 and 1 are one each), and \(V_3\) (all three counts one); the number of elements in the subarray \(a[1..2] = [1, 2]\) that are at most 2 is the value-range-\([1,2]\) count in \(V_3\) minus that count in \(V_1\), namely \(2 - 0 = 2\), and each version added exactly two new nodes on the path to the leaf it updated, sharing the rest.

Below the comparison model: van Emde Boas and y-fast tries

A comparison-based ordered structure needs \(\Omega(\log n)\) per operation, but when the keys are integers drawn from a bounded universe \(\{0, 1, \dots, u - 1\}\) the keys can be indexed rather than only compared, and the successor operation drops to \(O(\log \log u)\). The van Emde Boas tree achieves this by a recursion on the universe size rather than the number of elements. It splits the \(w\)-bit key into a high half and a low half, treating an element as living in cluster \(\lfloor x / \sqrt{u} \rfloor\) at position \(x \bmod \sqrt u\) within that cluster; a vEB structure of universe \(u\) stores the minimum and maximum of its set directly, a summary vEB of universe \(\sqrt u\) recording which clusters are nonempty, and \(\sqrt u\) child clusters each a vEB of universe \(\sqrt u\).

The trick that keeps the recursion shallow is storing the minimum outside the clusters, not inside them, so that a successor query recurses into at most one child. To find the successor of \(x\): if \(x\) is below the minimum, return the minimum in \(O(1)\); if \(x\)'s low half has a successor within \(x\)'s own cluster, which is checkable against that cluster's stored maximum, recurse once into that cluster; otherwise find the next nonempty cluster by a successor query in the summary structure and return that cluster's minimum, again one recursion. Every case makes at most one recursive call on a universe of size \(\sqrt u\), plus \(O(1)\) work, so the running time satisfies

Substituting \(u = 2^{w}\) turns the square root into halving the exponent, \(T(2^{w}) = T(2^{w/2}) + O(1)\); writing \(S(w) = T(2^{w})\) gives \(S(w) = S(w/2) + O(1) = O(\log w)\), and since \(w = \log_2 u\) this is \(T(u) = O(\log \log u)\). For a 32-bit universe the recursion depth is 5, and the tabulated values \(T(16) = 3, T(256) = 4, T(2^{16}) = 5, T(2^{32}) = 6\) track \(\log_2 \log_2 u\) exactly, confirming the bound. The catch is space: the naive vEB uses \(\Theta(u)\) bits regardless of how few keys it holds, because the cluster array is allocated for the whole universe. The y-fast trie of Willard (1983) repairs this to \(O(n)\) space at the cost of randomization. It first builds an x-fast trie, a binary trie over the \(w\)-bit keys with a hash table of the present prefixes at each level, so a successor query binary-searches over the \(w\) prefix lengths in \(O(\log w) = O(\log \log u)\) expected time; then it groups the \(n\) keys into \(\Theta(n / \log u)\) buckets of \(\Theta(\log u)\) consecutive keys each, stores only one representative per bucket in the x-fast trie, and keeps each bucket in a balanced tree of size \(O(\log u)\). The trie now holds \(O(n / \log u)\) representatives at \(O(\log u)\) space each, totaling \(O(n)\), and a successor is one \(O(\log \log u)\) trie query to find the bucket plus one \(O(\log \log u)\) search inside it.

Hashing theory

A hash table is only as good as its guarantee against collisions, and a fixed hash function has no guarantee at all: for any function an adversary can choose \(n\) keys that all collide. The repair is to choose the function at random from a family designed so that collisions are rare in expectation, which moves the worst case from over the inputs to over the random choice, exactly the move that makes quicksort with a random pivot robust.

Universal and \(k\)-wise independent families

A family \(\mathcal{H}\) of functions from a key universe to \(\{0, \dots, m - 1\}\) is universal if for every pair of distinct keys \(x \ne y\),

the collision probability of a uniformly random function. The canonical construction of Carter and Wegman (1979) picks a prime \(p\) larger than any key and sets \(h_{a,b}(x) = \bigl((a x + b) \bmod p\bigr) \bmod m\) with \(a\) drawn uniformly from \(\{1, \dots, p-1\}\) and \(b\) from \(\{0, \dots, p-1\}\). To see universality, fix \(x \ne y\) and consider the pair \((s, t) = (a x + b \bmod p,\ a y + b \bmod p)\); as \((a, b)\) ranges over its \((p-1)p\) choices, \((s, t)\) ranges over all pairs with \(s \ne t\) (since \(a \ne 0\) and \(x \ne y\) force \(s \ne t\)), each exactly once, because the map is a bijection on \(\mathbb{Z}_p^2\) restricted appropriately. A collision after the final mod \(m\) needs \(s \equiv t \pmod m\) with \(s \ne t\); for each of the \(p\) values of \(s\), the number of \(t \ne s\) with \(t \equiv s \pmod m\) is at most \(\lceil p/m \rceil - 1 \le (p-1)/m\), so the collision probability is at most \(\frac{p(p-1)/m}{p(p-1)} = \frac{1}{m}\), which is universality. The consequence is that the expected number of keys colliding with a given key, among \(n\) keys in \(m\) slots, is at most \((n-1)/m\), so with \(m = \Theta(n)\) a chained hash table has \(O(1)\) expected probe length. A stronger property, \(k\)-wise independence, requires that any \(k\) distinct keys map to independent uniform values; it is obtained by taking \(h(x) = \bigl(\sum_{i=0}^{k-1} a_i x^{i} \bmod p\bigr) \bmod m\), a random degree-\((k-1)\) polynomial, because \(k\) points determine such a polynomial uniquely and the coefficients are uniform. Higher independence is what concentration bounds for hashing need, and it is the property that Bloom-filter and count-sketch analyses lean on when they treat the hash outputs as independent.

Perfect hashing: the FKS two-level scheme

For a static set of \(n\) keys, known in advance, one can build a hash table with no collisions at all and \(O(1)\) worst-case lookup in \(O(n)\) space, which is the FKS construction of Fredman, Komlós, and Szemerédi (1984). It is a two-level scheme. The top level hashes the \(n\) keys into \(n\) buckets with a universal function; collisions are allowed here, and bucket \(i\) receives \(b_i\) keys. The bottom level resolves each bucket with its own universal function into a table of size \(b_i^2\); the reason \(b_i^2\) slots suffice to be collision-free with probability at least \(1/2\) is the birthday bound: with \(b_i\) keys in \(b_i^2\) slots, the expected number of colliding pairs is \(\binom{b_i}{2} / b_i^2 < 1/2\), so a random function is collision-free with probability over \(1/2\) and is found in \(O(1)\) expected tries. The space is dominated by \(\sum_i b_i^2\), and the key calculation bounds its expectation. With a universal top-level function into \(m = n\) buckets, \(\mathbb{E}\bigl[\sum_i b_i^2\bigr] = \mathbb{E}\bigl[\sum_i b_i\bigr] + 2\,\mathbb{E}\bigl[\sum_i \binom{b_i}{2}\bigr] = n + 2 \cdot \mathbb{E}[\text{colliding pairs}]\), and the expected number of colliding pairs is at most \(\binom{n}{2}/m = \binom{n}{2}/n < n/2\), so \(\mathbb{E}\bigl[\sum_i b_i^2\bigr] < n + 2 \cdot n/2 = 2n\). By Markov's inequality a random top function gives \(\sum_i b_i^2 < 4n\) with probability over \(1/2\), so a suitable top function is found in \(O(1)\) expected tries, and the total space is \(O(n)\) with two hash evaluations per lookup. The modern refinement is minimal perfect hashing, which maps \(n\) keys bijectively onto \(\{0, \dots, n-1\}\) in about 2 to 3 bits per key, and libraries such as those implementing the CHD and RecSplit algorithms hit that space in practice.

Cuckoo hashing

Cuckoo hashing gives \(O(1)\) worst-case lookup, not just expected, for a dynamic set, by giving each key exactly two candidate positions and guaranteeing it lives in one of them. In the two-table formulation of Pagh and Rodler (2004) there are two arrays and two hash functions \(h_1, h_2\); key \(x\) resides at \(h_1(x)\) in table 1 or \(h_2(x)\) in table 2, so a lookup probes exactly two cells and a delete is trivial. Insertion places \(x\) in one candidate; if the cell is occupied, the resident is evicted to its alternate cell, which may evict another key, and so on, a chain of displacements that walks the "cuckoo graph" whose vertices are cells and whose edges are keys. The scheme works because, below a load factor of \(1/2\) across the two tables, this graph almost never contains a component with two independent cycles, which is the only configuration that has more keys than cells and therefore cannot be placed; the probability of an unplaceable configuration is \(O(1/n)\) per insertion, and when it occurs the tables are rebuilt with fresh hash functions, costing \(O(n)\) but amortizing to \(O(1)\). The load factor is the crux: below \(1/2\) the cuckoo graph is subcritical and insertions terminate in \(O(1)\) expected displacements, while approaching \(1/2\) the expected chain length blows up, which is why practical variants use more than two hash functions or a bucketed layout with several slots per cell to push the safe load factor above \(0.9\). Blocked cuckoo hashing with a small stash is what sits under several high-performance hash tables today.

Bloom filters and the false-positive rate

A Bloom filter answers approximate set membership in space far below what storing the elements would take, at the price of one-sided error: it never reports a false negative but may report a false positive. It is an \(m\)-bit array, all zero initially, with \(k\) independent hash functions; inserting \(x\) sets the \(k\) bits \(h_1(x), \dots, h_k(x)\) to 1, and a membership test for \(y\) returns "present" only if all \(k\) of \(y\)'s bits are 1. A true member always passes, so no false negatives; a non-member passes only if all \(k\) of its bits happen to be set by other insertions, which is the false positive. After inserting \(n\) elements with \(k\) hash functions into \(m\) bits, treating the hashes as independent and uniform, the probability a specific bit is still zero is

using \((1 - 1/m)^{m} \to e^{-1}\). A false positive requires all \(k\) queried bits to be 1, and approximating those events as independent gives the false-positive rate

Minimizing over \(k\) for fixed \(m\) and \(n\): let \(p = e^{-kn/m}\), so \(f = (1 - p)^{k}\) and \(\ln f = k \ln(1 - p)\). Writing \(k = -\frac{m}{n} \ln p\) and substituting turns \(\ln f\) into a function of \(p\) alone, \(\ln f = -\frac{m}{n} \ln p \ln(1 - p)\), which is symmetric under \(p \mapsto 1 - p\) and is minimized at \(p = 1/2\). The optimal number of hash functions is therefore the one that makes each bit equally likely to be 0 or 1,

and at that setting \(f = (1/2)^{k^*} = (0.6185)^{m/n}\). Inverting for the space needed to hit a target rate \(f\) gives \(m/n = -\log_2 f / \ln 2 \approx 1.44 \log_2(1/f)\) bits per element, independent of the universe size and of the element size, which is the property that makes Bloom filters ubiquitous in storage engines. As a concrete check, with \(n = 1000\) elements and \(m = 10000\) bits, \(k^* = 10 \ln 2 \approx 6.93\), so \(k = 7\), giving \(f \approx (1 - e^{-0.7})^7 \approx 0.00819\), about one false positive in 122; using \(k = 5\) instead raises it to \(0.00943\) and \(k = 8\) to \(0.00846\), both worse than the optimum, confirming that seven hash functions is the right count here. The mining massive datasets page develops the streaming and sketching cousins, counting Bloom filters, cuckoo filters, and count-min sketches, that extend this idea to deletions and frequency estimation.

Succinct data structures

A succinct data structure stores an object in space equal to the information-theoretic minimum plus a lower-order term, while still supporting fast queries. The foundational primitive is a bitvector that answers rank and select. For a bit array \(B\) of length \(n\), \(\text{rank}_1(i)\) is the number of ones in \(B[0..i]\) and \(\text{select}_1(j)\) is the position of the \(j\)-th one; nearly every compact structure, from wavelet trees to compressed suffix arrays, is built by composing rank and select. The remarkable fact, due to Jacobson (1989), is that both can be answered in \(O(1)\) using only \(o(n)\) bits of extra space beyond the \(n\) bits of \(B\) itself.

The rank structure is a two-level index. Partition \(B\) into superblocks of length \(\log^2 n\) and store, for each, the cumulative rank up to its start; there are \(n / \log^2 n\) superblocks and each count is at most \(n\) needing \(\log n\) bits, for \(n \log n / \log^2 n = n / \log n = o(n)\) bits. Partition each superblock into blocks of length \(\tfrac12 \log n\) and store each block's rank relative to its superblock start; these relative counts are at most \(\log^2 n\) needing \(2\log\log n\) bits, and there are \(2n/\log n\) of them, totaling \(O(n \log\log n / \log n) = o(n)\) bits. The remaining in-block rank, over a block of \(\tfrac12 \log n\) bits, is read from a precomputed table indexed by the block's bit pattern and the offset; the table has \(2^{\frac12 \log n} = \sqrt n\) rows, negligible space. A rank query sums a superblock count, a block count, and a table lookup, three \(O(1)\) reads. Select is symmetric but slightly more involved, using a position-sampling index; the upshot is \(n + o(n)\) bits total supporting both in \(O(1)\), and the extra term really is lower order, so a billion-bit vector carries only tens of megabytes of index.

A wavelet tree lifts rank and select from bits to a sequence over an alphabet of size \(\sigma\), and in doing so becomes a compressed index for range queries and text. It recursively partitions the alphabet: the root stores one bit per sequence position recording whether that symbol falls in the lower or upper half of the alphabet, and the left and right children recurse on the subsequences of lower-half and upper-half symbols respectively, to depth \(\log \sigma\). Access, rank, and select of a symbol each walk one root-to-leaf path performing a bitvector rank at each level, costing \(O(\log \sigma)\); the total space is \(n \log \sigma\) bits, the entropy floor for the sequence, plus the \(o(\cdot)\) rank overhead. This single structure answers "how many times does symbol \(c\) appear in positions \([l, r]\)" and "what is the \(k\)-th smallest value in a subarray," which is why wavelet trees underpin compressed full-text indexes and column stores.

Implementation

The two structures worth having in muscle memory are the Fenwick tree and union-find, because they are short, they appear constantly, and they are easy to get subtly wrong. Both are shown below in C++ and Python; the C++ versions are the ones you would actually ship, and both were compiled or run on the array \(a = [3,1,4,1,5,9,2,6]\) and the union sequence from Problem 2, reproducing the hand computations: the Fenwick range \([2,6)\) sums to 19 and the union sequence collapses eight elements into one component.

#include <vector>
#include <cstdint>

// Fenwick / binary indexed tree over prefix sums.
// update: add delta at index i; prefix: sum of [0, i); range: sum of [l, r).
struct Fenwick {
    int n;
    std::vector<int64_t> t;               // 1-based internal array
    explicit Fenwick(int n) : n(n), t(n + 1, 0) {}

    void update(int i, int64_t delta) {   // i is 0-based
        for (++i; i <= n; i += i & (-i)) // add lowest set bit each step
            t[i] += delta;
    }
    int64_t prefix(int i) const {          // sum of a[0..i-1]
        int64_t s = 0;
        for (; i > 0; i -= i & (-i))     // strip lowest set bit each step
            s += t[i];
        return s;
    }
    int64_t range(int l, int r) const { return prefix(r) - prefix(l); }
};

// Usage:
//   int a[] = {3,1,4,1,5,9,2,6};
//   Fenwick f(8);
//   for (int i = 0; i < 8; ++i) f.update(i, a[i]);
//   f.range(2, 6);   // == 19

class Fenwick:
    """Binary indexed tree over prefix sums. O(log n) update and prefix."""
    def __init__(self, n: int) -> None:
        self.n = n
        self.t = [0] * (n + 1)            # 1-based internal array

    def update(self, i: int, delta: int) -> None:   # i is 0-based
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & (-i)                 # add lowest set bit

    def prefix(self, i: int) -> int:      # sum of a[0..i-1]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)                 # strip lowest set bit
        return s

    def range(self, l: int, r: int) -> int:
        return self.prefix(r) - self.prefix(l)


a = [3, 1, 4, 1, 5, 9, 2, 6]
f = Fenwick(len(a))
for i, v in enumerate(a):
    f.update(i, v)
assert f.range(2, 6) == 19               # 4 + 1 + 5 + 9
assert f.prefix(7) == 25                 # visits internal indices 7, 6, 4

pub struct Fenwick {
    n: usize,
    t: Vec<i64>, // 1-based internal array
}

impl Fenwick {
    pub fn new(n: usize) -> Self {
        Fenwick { n, t: vec![0; n + 1] }
    }
    pub fn update(&mut self, i: usize, delta: i64) { // i is 0-based
        let mut j = i + 1;
        while j <= self.n {
            self.t[j] += delta;
            j += j & j.wrapping_neg(); // add lowest set bit
        }
    }
    pub fn prefix(&self, i: usize) -> i64 { // sum of a[0..i]
        let mut s = 0;
        let mut j = i;
        while j > 0 {
            s += self.t[j];
            j -= j & j.wrapping_neg(); // strip lowest set bit
        }
        s
    }
    pub fn range(&self, l: usize, r: usize) -> i64 {
        self.prefix(r) - self.prefix(l)
    }
}

Union-find is worth showing with both heuristics in place, because the two-line combination of union by rank and path compression is what delivers the near-constant amortized cost proved above. The C++ find uses path halving, pointing each node at its grandparent as it walks, which is a single-pass variant of full path compression that gets the same asymptotic bound with less code and no recursion.

#include <vector>
#include <numeric>
#include <utility>

// Disjoint-set union with union by rank and path halving.
struct DSU {
    std::vector<int> parent, rank_;
    explicit DSU(int n) : parent(n), rank_(n, 0) {
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];  // path halving
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;           // already together
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;                      // attach shorter under taller
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
};

// Problem-2 sequence collapses {0..7} to a single component with root 0.

class DSU:
    """Disjoint-set union with union by rank and path halving."""
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.rank[a] < self.rank[b]:
            a, b = b, a
        self.parent[b] = a                  # attach shorter under taller
        if self.rank[a] == self.rank[b]:
            self.rank[a] += 1
        return True


d = DSU(8)
for a, b in [(0, 1), (2, 3), (0, 2), (4, 5), (6, 7), (4, 6), (0, 4)]:
    d.union(a, b)
assert len({d.find(i) for i in range(8)}) == 1     # one component
assert d.find(7) == 0                              # root is 0

pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<u32>,
}

impl Dsu {
    pub fn new(n: usize) -> Self {
        Dsu { parent: (0..n).collect(), rank: vec![0; n] }
    }
    pub fn find(&mut self, mut x: usize) -> usize {
        while self.parent[x] != x {
            self.parent[x] = self.parent[self.parent[x]]; // path halving
            x = self.parent[x];
        }
        x
    }
    pub fn union(&mut self, a: usize, b: usize) -> bool {
        let (mut a, mut b) = (self.find(a), self.find(b));
        if a == b {
            return false;
        }
        if self.rank[a] < self.rank[b] {
            std::mem::swap(&mut a, &mut b);
        }
        self.parent[b] = a;
        if self.rank[a] == self.rank[b] {
            self.rank[a] += 1;
        }
        true
    }
}

The amortized-analysis and hashing arguments are best believed by simulating them. The Python below measures the amortized cost of dynamic-array pushes and binary-counter increments against their proved bounds of 3 and 2, and then measures the empirical collision probability of the Carter-Wegman universal family against the \(1/m\) bound and the Bloom-filter false-positive rate against the formula, all of which match to within sampling noise on the values used earlier on this page.

import math, random

# --- amortized bounds by direct simulation -----------------------------------
def dynamic_array_cost(n_pushes: int) -> float:
    cost = cap = size = 0
    cap = 1
    for _ in range(n_pushes):
        if size == cap:          # resize: copy `size` then double
            cost += size
            cap *= 2
        cost += 1                # write the new element
        size += 1
    return cost / n_pushes       # amortized per push, proved <= 3

def counter_flips(n_incr: int) -> float:
    total = 0
    for x in range(n_incr):      # cost of incrementing x is popcount(x ^ (x+1))
        total += bin(x ^ (x + 1)).count("1")
    return total / n_incr        # amortized per increment, proved <= 2

print("dynamic array (n=17):", round(dynamic_array_cost(17), 3))   # 2.824
print("binary counter (n=16):", round(counter_flips(16), 3))       # 1.938

# --- universal hashing: empirical collision probability ----------------------
P = 2**31 - 1                    # a Mersenne prime > the universe
M = 97
def make_hash():
    a = random.randrange(1, P)
    b = random.randrange(0, P)
    return lambda x: ((a * x + b) % P) % M

x, y, trials, hits = 12345, 67890, 200_000, 0
for _ in range(trials):
    h = make_hash()
    hits += (h(x) == h(y))
print("collision prob:", round(hits / trials, 5), "bound 1/m:", round(1 / M, 5))

# --- Bloom filter false-positive rate ----------------------------------------
def bloom_fpr(n: int, m: int, k: int) -> float:
    return (1 - math.exp(-k * n / m)) ** k

n, m = 1000, 10000
k_star = round((m / n) * math.log(2))                 # optimal integer k = 7
print("optimal k:", k_star, "fpr:", round(bloom_fpr(n, m, k_star), 6))  # 0.008194

How it is done in practice

The gap between the derivations above and a deployed structure is almost entirely about the memory hierarchy, and the production versions look different from the textbook versions for that reason. The standard-library ordered map, libstdc++'s std::map, is a red-black tree exactly as derived, but the standard-library unordered map is where the interesting engineering lives: the libstdc++ std::unordered_map is required by the C++ standard's iterator-stability and bucket-interface guarantees to use chaining with node allocation, which costs a pointer-chase and a cache miss per lookup, and this is precisely why Google's absl::flat_hash_map and Meta's folly::F14 exist. Both abandon chaining for open addressing with a metadata array of one control byte per slot; a lookup hashes once, then a single SIMD instruction compares sixteen control bytes at a time against the key's fingerprint, resolving the probe inside one or two cache lines. The theoretical probe bound is unchanged, but the constant, measured in cache misses rather than comparisons, drops by a factor that makes these tables several times faster than the standard one on real workloads.

The succinct structures have made the same jump from theory to shipping code. The sdsl-lite library implements the rank/select bitvectors, wavelet trees, and compressed suffix arrays derived above with the constant factors tuned so the \(o(n)\) overhead is a few percent in practice, and it is the basis of production bioinformatics indexes over multi-gigabase genomes where the difference between \(n\) and \(2n\) bits decides whether the index fits in memory. Roaring bitmaps, in the CRoaring library, are the compressed-bitset structure under Apache Lucene, Elasticsearch, ClickHouse, and Druid; they partition a 32-bit key space into chunks and store each chunk as an array, a bitmap, or a run-length list depending on its density, an adaptive choice that keeps both space and boolean-operation time near optimal across the whole density range. Bloom filters and their variants gate the read path of every log-structured merge-tree store: RocksDB and LevelDB attach a filter to each sorted table so a point lookup that would otherwise touch every level's file skips the levels whose filter says the key is absent, turning a read from many disk seeks into one, and the choice of bits per key there is the exact tradeoff derived above, more bits for fewer wasted seeks. Fibonacci heaps, by contrast, are the cautionary tale in the other direction: their \(O(1)\) decrease-key is real but the constant factor and the pointer-chasing memory pattern make them slower than a simple binary heap on almost every real graph, so shortest-path codes overwhelmingly use a binary or \(d\)-ary heap despite the worse asymptotics, a reminder that an amortized bound is a promise about a sum, not about a cache.

The current research frontier

Three lines of recent work are worth tracking. The first is the pursuit of dynamic optimality, the conjecture that splay trees or some online binary search tree is constant-competitive with the offline optimum. Tango trees (Demaine, Harmon, Iacono, and Pătrașcu, 2007) established the first nontrivial \(O(\log\log n)\)-competitive online tree, and subsequent multi-splay and GreedyASS work by groups at MIT and CMU narrowed the geometric formulation of the problem due to Demaine, Harmon, Iacono, Kane, and Pătrașcu; the conjecture remains open and is one of the cleanest unsolved questions in the field. The second is learned and hybrid index structures, launched by the learned-index proposal of Kraska, Beutel, Chi, Dean, and Polyzotis at Google (2018), which replaces the internal nodes of a B-tree with a learned model that predicts a key's position; the follow-on RadixSpline, PGM-index of Ferragina and Vinciguerra (2020), and ALEX line of work made these updatable and gave worst-case guarantees, and the current question is when a learned index genuinely beats a well-tuned classical one rather than merely on a benign distribution. The third is filter and hashing structures beyond Bloom: the cuckoo filter of Fan, Andersen, Kaminsky, and Mitzenmacher (2014) supports deletion and packs better than a Bloom filter at low false-positive rates, the quotient filter and its RSQF variant underlie modern LSM stores, and the XOR filter and ribbon filter of Dietzfelbinger, Walzer, and collaborators (2019 onward) reach within a few percent of the information-theoretic space bound for a static filter, below what a Bloom filter can achieve. Across all three the theme is the same: the asymptotics were settled decades ago, and the frontier is the constant factor and the memory pattern that decide what actually runs fast.

Open source to read

• gcc-mirror/gcc (libstdc++) — the reference red-black tree is in libstdc++-v3/src/c++98/tree.cc and bits/stl_tree.h; reading the rebalance-after-erase code is the fastest way to see how few rotations a red-black delete really needs.
• abseil/abseil-cpp — the Swiss-table open-addressing hash map; start at absl/container/internal/raw_hash_set.h to see the control-byte metadata and the SIMD group probe that make it cache-resident.
• facebook/folly — the F14 hash tables in folly/container/F14Map.h and the F14Table.h internals, a second independent take on vectorized open addressing with a clear design-rationale comment block.
• boostorg/boost — Boost.Intrusive and Boost.MultiIndex for production balanced trees with intrusive hooks, and Boost.Unordered for a standards-conforming yet fast hash map; a good contrast with the standard library.
• simongog/sdsl-lite — the succinct data-structure library; include/sdsl/rank_support_v.hpp is the rank bitvector derived above, and wavelet_tree and csa_wt build the compressed indexes on top.
• RoaringBitmap/CRoaring — compressed bitmaps used across search and analytics engines; src/containers/ holds the array, bitset, and run containers and the logic that switches between them by density.
• wangyi-fudan/wyhash and google/cityhash — fast non-cryptographic hash functions used as the mixing step in the tables above; short enough to read in one sitting and understand the multiply-xor mixing.
• rust-lang/rust — the standard library's HashMap wraps hashbrown, a Rust port of the Swiss table, in library/std/src/collections/hash/; a clean, heavily commented modern implementation.

Common misconceptions

"Amortized means average-case." No. Amortized is a worst-case guarantee over a sequence, with no probability involved; a sequence of \(m\) dynamic-array pushes costs at most \(3m\) for every input, not on average. Average-case analysis, by contrast, averages over a distribution of inputs. A structure can be amortized \(O(1)\) and yet have a single operation cost \(\Theta(n)\); the guarantee is only that such operations are rare enough to be paid for.

"Fibonacci heaps make Dijkstra faster in practice." They improve the asymptotic bound to \(O(E + V\log V)\), but their large constant factors and pointer-chasing memory access make them slower than a binary heap on essentially every graph that fits in memory. The asymptotic win is real and the practical loss is also real; production shortest-path code uses simple heaps.

"A Bloom filter can give false negatives if it gets too full." It cannot, ever. A true member sets its \(k\) bits at insertion and those bits are never cleared, so a membership test for a true member always finds all \(k\) bits set. Overfilling raises the false-positive rate toward 1, degrading the filter to useless, but never produces a false negative. Only a counting Bloom filter that supports deletion can introduce false negatives, and only if an element is deleted that was never inserted.

"Path compression alone gives the inverse-Ackermann bound." Path compression without union by rank gives \(O(\log n)\) amortized, not \(O(\alpha(n))\); it is the combination of the two heuristics that is near-constant. Union by rank alone also gives only \(O(\log n)\), worst case per operation. Neither heuristic is dispensable for the tight bound.

"A sparse table works for any range query." It works in \(O(1)\) only for idempotent operations, min, max, and gcd, where the two overlapping blocks may double-cover the middle harmlessly. For a sum, the overlap is counted twice and the answer is wrong; sums need a segment tree or a Fenwick tree, which pay \(O(\log n)\) per query but tile the range without overlap.

"Universal hashing makes every lookup \(O(1)\)." It makes the expected probe length \(O(1)\), over the random choice of hash function, for any fixed set of keys. A particular random choice can still be bad, producing a long chain; the guarantee is in expectation, and worst-case \(O(1)\) lookup needs the stronger FKS perfect-hashing or cuckoo-hashing constructions.

"Succinct and compressed mean the same thing." A succinct structure uses the information-theoretic minimum plus a lower-order term while supporting queries in the same time as the non-succinct version; a compressed structure exploits redundancy in the specific input to go below the worst-case minimum, often at some query cost. A rank/select bitvector is succinct; a run-length-encoded bitmap is compressed. The distinction matters because the succinct bound holds for the worst-case input and the compressed bound does not.

Self-check

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, 3rd edition. MIT Press. Chapters on amortized analysis, van Emde Boas trees, disjoint sets, and augmented data structures.
2. Tarjan, R. E. (1983). Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM. doi:10.1137/1.9781611970265.
3. Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215–225. doi:10.1145/321879.321884.
4. Sleator, D. D., and Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652–686. doi:10.1145/3828.3835.
5. Fredman, M. L., and Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615. doi:10.1145/28869.28874.
6. Driscoll, J. R., Sarnak, N., Sleator, D. D., and Tarjan, R. E. (1989). Making data structures persistent. Journal of Computer and System Sciences, 38(1), 86–124. doi:10.1016/0022-0000(89)90034-2.
7. van Emde Boas, P. (1975). Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), 75–84. doi:10.1109/SFCS.1975.26.
8. Fredman, M. L., Komlós, J., and Szemerédi, E. (1984). Storing a sparse table with \(O(1)\) worst case access time. Journal of the ACM, 31(3), 538–544. doi:10.1145/828.1884.
9. Carter, J. L., and Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143–154. doi:10.1016/0022-0000(79)90044-8.
10. Pagh, R., and Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144. doi:10.1016/j.jalgor.2003.12.002.
11. Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422–426. doi:10.1145/362686.362692.
12. Jacobson, G. (1989). Space-efficient static trees and graphs. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 549–554. doi:10.1109/SFCS.1989.63533.
13. Navarro, G. (2016). Compact Data Structures: A Practical Approach. Cambridge University Press. doi:10.1017/CBO9781316588284.
14. Fischer, J., and Heun, V. (2006). Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In Combinatorial Pattern Matching (CPM), LNCS 4009, 36–48. doi:10.1007/11780441_5.
15. Willard, D. E. (1983). Log-logarithmic worst-case range queries are possible in space \(\Theta(N)\). Information Processing Letters, 17(2), 81–84. doi:10.1016/0020-0190(83)90075-3.
16. Demaine, E. D., Harmon, D., Iacono, J., and Pătrașcu, M. (2007). Dynamic optimality — almost. SIAM Journal on Computing, 37(1), 240–251. doi:10.1137/S0097539705447347.
17. Ferragina, P., and Vinciguerra, G. (2020). The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 13(8), 1162–1175. doi:10.14778/3389133.3389135.
18. Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. (2018). The case for learned index structures. In Proceedings of SIGMOD 2018, 489–504. doi:10.1145/3183713.3196909.
19. Fan, B., Andersen, D. G., Kaminsky, M., and Mitzenmacher, M. (2014). Cuckoo filter: practically better than Bloom. In Proceedings of CoNEXT 2014, 75–88. doi:10.1145/2674005.2674994.
20. Fredman, M., and Saks, M. (1989). The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 345–354. doi:10.1145/73007.73040.