A list, queue, or map is an interface contract before it is an array, linked sequence, or hash table. Keeping the abstract type separate from its representation lets a workload choose a different implementation without changing callers.

Operations are correct because they preserve the invariant: an ordered tree keeps keys in order, a ring buffer keeps its head and tail within the capacity convention, and a map keeps equality and hashing consistent.

A dynamic array can copy many elements on one append while still spending constant total work per append across a long sequence of geometric growth. The occasional expensive operation remains a possible latency spike.

Load factor controls collision and probe behaviour, but its meaning depends on the scheme: chaining counts stored entries per bucket, while open addressing counts occupied slots and may also track tombstones.

Path copying updates only the nodes on a changed root-to-leaf path and lets older roots remain readable. The memory bill is proportional to copied paths plus the retained versions, not to a full duplicate of every version.

A lookup structure is not “fast” in the abstract. State whether the workload is read-heavy, update-heavy, ordered, bursty, or memory-bound, and whether the measurement counts comparisons, bytes, cache misses, allocations, or end-to-end latency.

Amortized analysis chooses a non-negative state measure whose change explains the debt or credit carried between operations. The potential argument is a sequence proof; it is not a percentile or a per-request latency bound.

A factor greater than one creates slack for future appends. The factor controls memory overhead and copy frequency, while separate shrink and grow thresholds prevent oscillation around a boundary.

If head equals tail and no count is stored, the same indices can describe both states. Reserving one slot makes one state unreachable; storing a count is an alternative representation with a different invariant.

Edits add a piece descriptor rather than rewriting the original text. The structure is attractive for undo and stable source storage, but many pieces require indexing and coalescing policies.

Equal keys must hash to compatible buckets, keys must not change their equality-relevant fields while resident, and lookup must search every location the collision scheme can reach. Expected bounds depend on the hashing and load assumptions.

An empty slot can terminate a probe, while a tombstone says “continue searching but this slot may be reused.” Tombstone accumulation increases probe cost, so a production table tracks cleanup or rehash thresholds.

Swiss-style tables store control bytes beside groups of slots. A matching fingerprint is only a candidate: equality on the full key still decides membership. Fingerprint width trades metadata space against candidate rate.

The map finds a record and the linked order detaches and appends it. Both structures must be updated atomically with respect to the cache operation; a stale map pointer or list link breaks eviction correctness.

A rotation preserves search order while repairing height metadata. The bound comes from the invariant at every node, not from the fact that a tree “usually looks balanced.”

No root-to-leaf path may have adjacent red nodes, and all such paths have the same black height. Together these rules prevent a path from becoming more than a constant factor longer than the shortest one.

A node promoted to level k appears with probability p^k. Independent promotion gives an expected logarithmic search path, but not a logarithmic worst-case guarantee.

Store a summary such as subtree size and recompute it after every rotation or link change. The augmentation is correct only when the update path repairs every affected summary.

Higher fanout reduces levels and pointer hops but increases in-node search and split work. An in-memory B-tree should expose this as a layout trade-off, not borrow a page-oriented cost model without qualification.

Segment-tree queries return the identity for disjoint ranges. Associativity is what permits regrouping; commutativity is not required, so a string-concatenation tree must preserve left-to-right order.

A tag needs a composition rule and enough summary metadata to update a node without descending. Assignment and addition do not commute, so push order is part of correctness.

Prefix enumeration and suffix searches cannot return z matches in less than Ω(z) output work. State the query length and output size separately instead of promising a single logarithmic bound.

Bitmap-indexed hash tries use rank to avoid allocating a full child array. The bitmap tests membership; rank computes the compact offset after membership is known.

Record the owner, field, and old value before mutation. Reverse-order restoration is correct when updates are nested; arbitrary version reads require a broader persistence design.

A Bloom filter may say “possibly present” for an absent key, but a zero bit proves absence under its current contents. The error budget must be stated with the population and hash assumptions that produced it.

Relocation follows an alternating candidate sequence and may cycle. A bounded kick budget plus a rebuild policy is part of the insertion contract; a successful lookup still needs a full membership interpretation.

With non-negative updates, collisions only increase counters, so the minimum is an upper estimate. Width controls additive error and depth controls failure probability under the stated hash model.

Each register retains the most extreme hash rank observed. Union is register-wise maximum; the estimator, bias correction, and small-range regime remain part of the metric contract.

If a query region is disjoint from a child bound, no descendant can qualify. Overlap makes search branch, so enclosure proves correctness but does not promise a logarithmic query.

Succinct is a space-and-operations claim, not a synonym for compressed bytes. Rank/select and topology structures spend auxiliary bits to make navigation fast.

The generation changes whenever a slot is reclaimed. A stale handle may still name the same numeric slot, but the generation mismatch makes the invalid reference observable instead of silently aliasing a new object.

A concurrent container needs both an atomic ownership protocol and a memory-ordering argument. “Thread-safe” is too broad: specify SPSC, MPSC, or another supported access pattern and the progress guarantee.

Include or exclude allocation, hashing, serialization, synchronization, warm-up, and output materialization deliberately. A mean without workload, percentiles, and boundary is not a portable performance claim.

A codebook reduces storage or distance work at the cost of reconstruction error. Index quality must report the distance metric, codebook training population, recall target, and memory per vector together.

Associativity preserves element order while changing parentheses. It does not imply commutativity, inverses, idempotence, or a constant-time combine.

Minimum and maximum tolerate the duplicated overlap in a two-block sparse-table query; addition does not.

The identity represents an empty interval. Segment queries combine disjoint blocks in order, so they require no inverse and no commutativity.

Inverses let a prefix summary be cancelled: the range summary is the inverse of the left prefix combined, on the left, with the right prefix. A commutative (abelian) group also lets the inverse go on either side; integer addition and XOR are commutative groups, minimum is not a group.

Linearithmic storage and construction buy constant-time queries when overlapping blocks use an idempotent combine. Frequent corrections invalidate the static workload assumption.

One-based cell i stores (i-lowbit(i),i]. Prefix queries subtract the low bit; point additions add it to reach containing blocks.

Adding to an interval changes its start difference and the difference after its end. One Fenwick tree over differences supports range addition and point lookup; range totals need an additional weighted tree.

Addition uses (1,d), assignment uses (0,c), and identity uses (1,0). New tags compose after old tags; a node summary already reflects its pending action.

Lower bounds translate absent query endpoints correctly. Ranks preserve order and equality, not distances; new coordinates may require rebuilding the index.

A node stands for a prefix whether or not a key terminates at it, so existence alone cannot answer membership. The marker is what lets one key be a prefix of another while both remain present; the sentinel-$ convention achieves the same by ending every key at a leaf.

A chain of single-child trie nodes decides nothing, so a radix tree merges it into one edge with a substring label. Lookup compares whole labels rather than one character per level, and insertion must handle the three ways a match can end inside an edge.

In a suffix array, comparisons cost the pattern length because each probe re-reads the shared prefix; LCP values between neighbours are what later algorithms and accelerations exploit. The symbol LCP names an array of adjacent-prefix lengths.

Following a suffix link drops one character of context, which is what makes on-line construction walk the boundary path in amortised constant steps per suffix. The tree answers substring, repeat, and coverage questions that the flat suffix array only answers with extra machinery.

A matrix makes membership an address computation but spends a cell per possible edge; adjacency lists index the relation by source so a scan costs the out-degree, not the vertex count. Adding the reverse direction or cheap membership is a separate purchase in each layout.

Compressed sparse layouts store all rows in one contiguous values array; offsets[i] to offsets[i+1] mark row i. Row access is two lookups plus a scan proportional to the row, and a write to an earlier row shifts every later entry.

The find pays once to flatten the path it walked; later finds on those nodes are short. Combined with a linking rule that keeps trees shallow, the amortised bound is inverse-Ackermann — the compression itself is what makes the bound amortised rather than worst-case.

Rank upper-bounds tree height and only grows when two equal ranks merge, which keeps any single find logarithmic before compression is even considered. Union by size is the same argument measured in nodes instead of levels.

A rank error of εN is not a value error: the returned item is guaranteed close in position, and its value can still be far if the distribution is steep. Mergeable sketches maintain the guarantee by keeping weighted items and compacting levels only when capacity forces it.

A nearest-neighbour query descends to the cell containing q, then requires each skipped cell to prove its distance bound cannot beat the incumbent. The pruning argument weakens as the dimension grows because the bounds stop discriminating.

Proximity-graph indexes answer approximate nearest queries by greedily descending a layered neighbour graph. The search cost is a conditional claim: it is logarithmic only while the routing keeps making progress, and the structure offers no unconditional bound.

A wavelet tree writes one bit per position per level, telling whether the symbol goes left or right; rank/select on the level bitmaps tracks the position window downward. The matrix stores the same levels flat without pointers.

Level-order topology writes a 1 for each child and a 0 per node boundary, then navigates with rank and select instead of pointers. The encoding spends about two bits per node; locality and update cost are the honest losses.

When several structures share one workload, costs must be counted in one unit — here touches — and charged to the hour, not quoted asymptotically. The ledger is what lets a sorted array beat a trie on one line while losing the composition overall.

A one-sided sketch can fire alerts a true breach never caused, but only inside a narrow band below the threshold. Keeping exact counts for the bounded key set that matters turns the sketch from a counter into a screen plus a decider.

Indexing every version pays a build per commit; indexing none pays a scan per query. The break-even query count splits the retained versions into a hot set worth protecting and a cold set served by the shared structure.

Operations: index O(1), append amortized O(1), middle insertion O(n). Memory: contiguous capacity with bounded slack. Locality: excellent for scans. Mutation: reallocation can invalidate addresses. Workload fit: dense sequences with frequent reads and end appends.

Operations: expected O(1) lookup, insert, and delete; no ordered range traversal. Memory: spare slots or bucket metadata. Locality: open addressing is often better than pointer chains. Mutation: rehashing moves entries unless handles add indirection. Workload fit: equality-keyed access with a stable hash contract.

Operations: O(log n) search and updates, output-sensitive ranges. Memory: one node plus metadata per element. Locality: weaker than flat arrays but preserves order. Mutation: rotations move links and may change node addresses. Workload fit: ordered access, ranges, and updates that cannot tolerate hash-table disorder.

Operations: O(log n) point update and prefix query, with range sums obtained by subtraction when an inverse exists. Memory: O(n) compact array. Locality: predictable array accesses. Mutation: supports point updates, not arbitrary range updates without an added technique. Workload fit: numeric prefix/range aggregates over a fixed index domain.

Operations: prefix lookup and enumeration proportional to key characters plus output. Memory: nodes and child metadata can dominate. Locality: depends on child representation. Mutation: insertion preserves other prefixes but may allocate many nodes. Workload fit: autocomplete, routing, or dictionaries where prefixes are first-class queries.

Operations: unlink or insert beside a known node O(1), index lookup O(n). Memory: one node and links per element. Locality: pointer chasing is weak. Mutation: node addresses can remain stable while the sequence changes. Workload fit: splice-heavy workloads with handles, not random indexing.

Operations: enqueue/dequeue O(1) when not full or empty. Memory: fixed capacity. Locality: contiguous and cache-friendly. Mutation: overwrite, reject, or block at full capacity must be explicit. Workload fit: telemetry, audio, and producer-consumer queues with a hard bound.

Operations: expected constant-time lookup while load and tombstones are controlled. Memory: no per-entry links but spare slots are required. Locality: strong group locality. Mutation: deletion needs tombstones or a correct repair scheme; resize moves entries. Workload fit: dense, cache-sensitive maps with stable hash keys.

Operations: expected lookup and update cost depends on load and group scans. Memory: control metadata plus slots. Locality: excellent for group probes. Mutation: fingerprints reject candidates but full-key equality remains authoritative. Workload fit: high-throughput in-memory maps where cache traffic matters.

Operations: lookup, touch, insert, and eviction O(1) with a hash map plus linked order. Memory: one map record and order node per entry. Locality: mixed. Mutation: map and order updates must stay consistent. Workload fit: recency-based eviction; the policy is not a universal popularity predictor.

Operations: O(log n) search and updates with rotations. Memory: nodes plus height metadata. Locality: weaker than arrays and flat tables. Mutation: rotations change links and may change node relationships. Workload fit: ordered updates where tighter height matters more than update simplicity.

Operations: O(log n) worst-case search and updates. Memory: one color bit or field per node. Locality: pointer-based. Mutation: fix-up rotations and recoloring preserve the black-height contract. Workload fit: general ordered maps and sets with stable worst-case bounds.

Operations: expected O(log n) search and update, O(n) worst case. Memory: multiple forward links with expected constant height per node. Locality: pointer-based. Mutation: random level choices affect shape. Workload fit: ordered indexes where simple implementation and concurrency-friendly local updates are valuable.

Operations: O(log_f n) levels plus in-node work. Memory: packed nodes and separators. Locality: better than binary pointer trees when nodes fit the cache target. Mutation: split/merge policies affect layout and iterator stability. Workload fit: large in-memory ordered maps with locality-sensitive traversal.

Operations: peek O(1), push/pop O(log n), bottom-up build O(n). Memory: compact array. Locality: strong along heap paths. Mutation: arbitrary deletion needs an index or lazy removal. Workload fit: one active priority frontier without meld or direct key updates.

Operations: change-key and cancellation O(log n), position lookup expected O(1). Memory: heap entries plus an index map. Locality: mixed. Mutation: every swap must repair both representations. Workload fit: schedulers and graph algorithms that update known priorities.

Operations: iteration is proportional to stored entries, while random access may require an index or a search. Memory: O(nnz) values plus offsets, where nnz is the number of non-zeros. Locality: excellent for packed scans. Mutation: insertions can shift or rebuild packed regions. Workload fit: sparse graphs, matrices, and inverted layouts where empty space dominates.

Operations: point update and range query O(log n), with lazy tags for compatible range updates. Memory: O(n) summaries and tags. Locality: tree-array dependent. Mutation: combine order, identity, and tag composition are part of the API. Workload fit: dynamic intervals with a defined algebra.

Operations: binary search over suffixes, with comparison cost tied to pattern length and result output. Memory: offsets plus construction workspace. Locality: compact query index. Mutation: updates require rebuilding or a dynamic companion. Workload fit: static text corpora and substring queries where a compact index is preferred.

Operations: union/find with rank or size and path compression O(α(n)) amortized. Memory: parent and rank/size arrays. Locality: array-based pointer chasing. Mutation: arbitrary deletion and rollback require different contracts. Workload fit: incremental connectivity and component labeling.

Operations: query old roots without locks; update cost O(h) new nodes. Memory: proportional to copied paths plus retained roots. Locality: shared immutable nodes. Mutation: versions are new roots, and reclamation needs lifetime ownership. Workload fit: snapshots, undo, MVCC-like reads, and branching histories.

Operations: O(k) bit probes and updates. Memory: bits per expected item. Locality: compact bit array. Mutation: ordinary deletion is unsupported; saturation raises false positives. Workload fit: avoid expensive exact lookups when a false positive is tolerable but a false negative is not.

Operations: O(d) update/query and merge by aligned counter addition. Memory: d×w counters. Locality: row probes. Mutation: error grows with unplanned population and signed updates need a different estimator. Workload fit: non-negative event frequencies and heavy-hitter candidate generation.

Operations: O(1) register update/query after hashing; union is a maximum per register. Memory: m small registers. Locality: compact. Mutation: estimator bias and small-cardinality correction are part of the metric. Workload fit: cardinality metrics where exact sets are too large.

Operations: fast nearest queries on favorable low-dimensional distributions, with no unconditional logarithmic promise. Memory: points and region metadata. Locality: recursive regions. Mutation: skew can require rebuilding. Workload fit: low-dimensional points and workloads where exact distance is required.

Operations: intersection and containment search depends on overlap and split quality. Memory: object bounds and hierarchy metadata. Locality: node-dependent. Mutation: insertion and split policy directly determine future overlap. Workload fit: rectangles, map objects, and spatial extents rather than only points.

Operations: rank/select and symbol-range queries depend on alphabet height. Memory: sequence-dependent succinct representation plus rank support. Locality: layered bitvector access. Mutation: dynamic updates are a separate engineering problem. Workload fit: static compressed indexes over text or integer sequences.

Operations: enqueue/dequeue O(1) when capacity is available. Memory: fixed slots plus producer/consumer indices. Locality: contiguous. Mutation: correctness depends on ownership and release/acquire publication; the contract does not imply MPSC safety. Workload fit: one producer and one consumer crossing a thread boundary.

Operations: O(n) build, O(1) range sum. Memory: n+1 totals. Locality: sequential construction and two boundary reads. Mutation: point corrections invalidate later prefixes. Workload fit: immutable or batch-published exact sums.

Operations: O(n log n) construction, O(1) idempotent range query. Memory: O(n log n) summaries. Locality: contiguous rows, two query reads. Mutation: many overlapping blocks can be invalidated. Workload fit: frequent static minima or maxima with enough memory.

Operations: O(log n) range assignment, addition, and sum; O(n) build. Memory: O(n) sums and fixed-size tags. Locality: array tree with extra tag accesses. Mutation: queries can push tags; assignment and addition compose in chronological order. Workload fit: online mixed interval mutations.

Operations: O(n log n) sorting, O(log n) boundary translation plus range-index cost. Memory: O(n) coordinates plus chosen summaries. Locality: packed ordered coordinates. Mutation: new coordinates can invalidate ranks. Workload fit: known sparse point coordinates; preserve real gaps separately for duration or area.

Operations: lookup compares whole edge labels, cost proportional to key characters plus label compares rather than one node per character. Memory: far fewer nodes than an uncompressed trie when paths are sparse. Locality: fewer pointer hops, but edges carry variable-length labels. Mutation: insertion splits an edge in one of three ways; deletion merges. Workload fit: sparse key spaces and long shared prefixes where the plain trie wastes nodes.

Operations: substring, repeat, and coverage queries answered at the structure; on-line build walks boundary suffix links. Memory: linear in text length but with much larger constants than a suffix array. Locality: pointer-heavy unless flattened. Mutation: built for a fixed text. Workload fit: repeated structural queries over one corpus where the suffix array’s extra machinery costs more than the tree’s space.

Operations: membership is an address computation in a matrix and a scan in lists; neighbor iteration costs out-degree, not vertex count, in lists. Memory: matrix spends a cell per possible edge; lists spend the stored edges. Locality: lists chase per-vertex storage. Mutation: adding the reverse direction or cheap membership is a separate purchase in each layout. Workload fit: chosen by density and which direction scans must serve.

Operations: row access is two offset lookups plus a scan of the row; construction is a prefix sum and a scatter. Memory: values plus per-row offsets, nothing per empty cell. Locality: excellent for sequential row scans. Mutation: writing an early row shifts later entries; edits favor rebuild-at-batch policies. Workload fit: sparse graphs and matrices read far more often than written.

Operations: lookup and update follow hash fragments to bitmap-indexed child slots; updates copy only the path. Memory: nodes exist only where key fragments differ, and old roots stay readable. Locality: dense child arrays via bitmap rank. Mutation: every write yields a new root; reclamation is a lifetime-policy question. Workload fit: persistent maps and sets needing version reads alongside updates.

Operations: record before mutation, restore in reverse order; each replayed record returns one field to its old value. Memory: one record per mutation since the checkpoint. Locality: sequential journal. Mutation: nested updates roll back correctly; arbitrary version reads need full persistence instead. Workload fit: search, backtracking, and transactional sections where undo scope is strictly nested.

Operations: lookup checks two candidate buckets for a fingerprint; insert relocates occupants along an alternating path up to a kick limit, then must rebuild or reject. Memory: fingerprints only, denser than a Bloom filter at low false-positive rates. Locality: two bucket probes. Mutation: deletion removes a fingerprint — permitted where Bloom deletes are not; occupancy has a hard ceiling. Workload fit: membership screens that must delete and tolerate false positives.

Operations: insert and merge keep weighted items; compaction between levels spends capacity only when forced. Memory: sized by the error target, not the stream length. Locality: buffer flushes. Mutation: rank error εN is positional, not a value guarantee. Workload fit: latency percentiles and order statistics over streams too large to sort.

Operations: query descends layers greedily to a local minimum with a candidate frontier; insertion picks neighbors and prunes to a degree bound. Memory: per-vector links plus the vectors themselves. Locality: pointer-like edge walks. Mutation: cost bounds are conditional on routing progress — no unconditional logarithm. Workload fit: high-dimensional approximate nearest-neighbor indexes where recall and latency are tuned jointly.

Operations: distance is approximated through codewords; index quality reports metric, training population, and recall together. Memory: compressed codes per vector plus the codebook. Locality: packed code scans. Mutation: retraining or recall drift is an operational cost. Workload fit: vector search where reconstruction error is acceptable for memory and speed.

Operations: rank(i) counts set bits below a position; select(j) finds the j-th set bit; both O(1) with o(n) extra bits. Memory: the raw bits plus sparse and dense auxiliary layers. Locality: block-indexed lookups. Mutation: auxiliary layers are build-time data — the structure is static by contract. Workload fit: the support layer under every succinct representation.

Operations: parent, child, and degree are rank/select computations over the bitvector. Memory: about two bits per node plus the auxiliary indexes — far under a pointer per edge. Locality: sequential bit access. Mutation: the encoding is static; edits mean rebuilds. Workload fit: large fixed trees where pointer storage is the cost driver.

Operations: dereference validates the slot’s generation against the handle’s; reuse bumps the generation so a stale handle mismatches instead of aliasing. Memory: one generation field per slot. Locality: one extra indirection per access. Mutation: slot recycling is safe by construction; counter wrap needs a stated bound. Workload fit: long-lived handles into mutating tables — entity stores, caches, callbacks.

Operations: the benchmark fixes the operation mix, key distribution, warmup, and measurement boundary before a number is reported. Memory: measured as part of the result, not ignored. Locality: not applicable — the point is the claim. Mutation: an unrepresentative benchmark is worse than none because it prices the wrong workload. Workload fit: every comparison a design decision turns on.