The Segment Tree
Each node stores the sum of an interval, so a range query combines O(log n) precomputed pieces and a point update repairs one root-to-leaf path, while lazy propagation extends the same tree to range updates. The Solve it task builds an iterative tree in a flat array of size 2n, the version to reach for in Range Sum Query Mutable or any range-min or range-max question with updates.
Bits Do the Walking: Fenwick Tree
A binary indexed tree packs partial sums into one 1-based array, and the i & -i trick decides which block each cell owns, so a prefix query walks down and an update walks up, both in O(log n). You implement update and prefix_sum, which prepares you for counting inversions, rank queries over a changing set, and the question of when a Fenwick tree beats a segment tree.
How Databases Stay Balanced: B-Trees
Watch a node overflow at its fourth key, split, and push its median up to the parent, which is why a B-tree only grows at the root and every leaf stays at the same depth. Implementing insert, search and height with minimum degree 3 prepares you to explain why database indexes use B-trees rather than binary trees: many keys per disk page means three or four reads instead of thirty.
Express Lanes: The Skip List
A sorted linked list gains express lanes: each node rises to extra levels by coin flip, so a search goes right while it can and drops a level when it would overshoot, for O(log n) expected time with no rebalancing. You implement insert, search and delete with a seeded coin, which prepares you to explain why Redis sorted sets and LSM-tree memtables use skip lists instead of balanced trees.
Two Nodes, Climbing to Meet: LCA with Binary Lifting
Precompute a table in which each node's 2^k-th ancestor is two jumps of 2^(k-1), bring both nodes to the same depth, then lift them together until their parents meet. Building that table and answering queries in O(log n) prepares you for lowest-common-ancestor queries on large trees, the distance between two nodes, and the jump-pointer trick behind k-th ancestor problems.
The Non-Backtracker: KMP
KMP first builds the LPS table, the longest prefix of the pattern that is also a suffix at each position, then scans the text without ever moving its pointer backward, for O(n + m) in total. Writing kmp_search to return every overlapping match prepares you for Find the Index of the First Occurrence, Repeated Substring Pattern and Shortest Palindrome, where the LPS table is the real trick.
One Pass, Every Word: Aho-Corasick
Build a trie of every pattern, wire failure links by BFS so a mismatch falls back to the longest matching suffix, and scan the text once to report every occurrence. Your find_all has to count overlapping matches, the detail that separates it from running KMP once per word, and the same structure sits behind keyword filters, signature scanning and Stream of Characters style problems.
Cycles Into Components: Tarjan’s SCC
One depth-first search stamps each node with an index and a low-link value, pulls low down along back edges, and pops a whole strongly connected component off the stack whenever it finds a root. Returning the components of a directed graph prepares you for 2-SAT, for condensing cycles into a DAG before a topological sort, and for Critical Connections in a Network, where the same low-link idea finds bridges.
Pushing Water Through Pipes: Dinic’s Max-Flow
Dinic's algorithm alternates a BFS that builds a level graph with DFS passes that push a blocking flow, storing each edge beside its reverse so e ^ 1 finds the partner. Implementing max_flow prepares you to spot the problems that are flow in disguise, such as bipartite matching, assignment and project selection, and to explain why the maximum flow equals the minimum cut.
Fibonacci Fast-Forwarded: Matrix Exponentiation
The Fibonacci recurrence becomes a 2×2 matrix raised to the n-th power, and squaring the base while reading n in binary computes it in O(log n) multiplications instead of n additions. Building mat_mult, mat_pow and fib prepares you for nth-term questions on any linear recurrence, such as climbing-stairs variants or counting paths of length k in a graph, usually asked modulo a prime.
Halving the Exponential: Meet in the Middle
Subset sum over n items is 2^n by brute force, so split the items in half, enumerate each half's sums into a frequency map, and match complements, for about 2^(n/2) work per side. The count_subsets task prepares you for problems with n around 40 whose values are too large for a knapsack table, such as Partition Array Into Two Arrays to Minimize Sum Difference.
Counting a Crowd in Kilobytes: HyperLogLog
Hash each item, let a few bits pick a register, keep the longest run of leading zeros each register has seen, and combine the registers with a harmonic mean to estimate distinct counts to within about 1% in kilobytes. You implement build and estimate with the small-range correction, which prepares you for design questions like counting unique visitors, where an exact set would cost gigabytes.
The Fair Draw: Reservoir Sampling
Keep the first item, then replace it with the i-th item with probability 1/i, and the held item stays uniformly random at every point in a stream whose length you never learn. You implement both the one-item and k-item reservoirs with an injected random function, which prepares you for Linked List Random Node, sampling log lines at scale, and the fairness proof interviewers ask for.