i. Containers, Hashing and Choosing a Structure

What the standard containers really cost, how to hash safely and fast, and a decision map to pick the right structure for a query pattern. Per-container API details are in C++ for CP.

Real costs

Container	Notes
vector	contiguous; growth doubles capacity, so push_back is amortized $O(1)$ but may invalidate references; reserve when the size is known
array-backed stack / queue	a vector plus a head index beats std::queue (which is a deque)
deque	blocks of 512 bytes; $O(1)$ at both ends; about 2x slower than vector and has a big per-instance overhead (avoid vector<deque> with $10^5$ instances)
list	almost never: one allocation per node, no locality. Use an array-based linked list (nxt[i], prv[i]) when you need $O(1)$ unlink
set/map	red-black tree, ~40-50 bytes per node, cache-unfriendly; $O(\log n)$ with a constant around 10x a sorted vector
priority_queue	binary heap over a vector; fast
unordered_map	chaining, one allocation per node; slow constant, hackable

Array-based linked list (for “delete element, find neighbours” simulations, like removing elements in order and asking for the new neighbours):

vector<int> L(n), R(n);
for (int i = 0; i < n; i++) L[i] = i - 1, R[i] = i + 1;
auto erase = [&](int i) { if (L[i] >= 0) R[L[i]] = R[i]; if (R[i] < n) L[R[i]] = L[i]; };

Processing deletions in reverse turns them into insertions, which sometimes removes the need for a balanced tree.

Hashing

Option	Speed	Notes
sort + lower_bound / compress to [0, m)	fastest	when all keys are known in advance
gp_hash_table<K, V, SafeHash> (PBDS)	3-5x faster than unordered_map	open addressing
unordered_map<K, V, SafeHash> + reserve + max_load_factor(0.25)	ok
hand-written linear probing	fastest dynamic	fixed capacity, power of two, keep load $\le 0.5$

Always randomise the hash (splitmix64 with a time seed, see C++ for CP). On Codeforces anti-hash tests target the default identity hash and even fixed custom hashes.

template<class V> struct HashMap {                     // u64 keys, linear probing, no erase
    vector<ull> k; vector<V> v; vector<char> used; ull mask, seed;
    HashMap(int lg) : k(1 << lg), v(1 << lg), used(1 << lg), mask((1 << lg) - 1),
        seed(chrono::steady_clock::now().time_since_epoch().count()) {}
    static ull mix(ull x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
    V& operator[](ull key) {
        ull i = mix(key + seed) & mask;
        while (used[i] && k[i] != key) i = (i + 1) & mask;
        if (!used[i]) used[i] = 1, k[i] = key, v[i] = V();
        return v[i];
    }
};

Erasing from linear probing: use backward-shift deletion (move later entries of the same cluster back if their home slot permits) instead of tombstones.

Hashing composite keys: for pairs (a, b) of 32-bit values, use (ull)a << 32 | b. For vectors or sets, use polynomial or sum-of-random-values hashing (set hashing).

Bloom filter: $m$ bits, $k$ hashes, $n$ keys gives a false-positive rate $\approx (1-e^{-kn/m}{)}^k$, minimised at $k=\frac{m}{n}\ln 2$ (about 0.6% at 10 bits per key). No false negatives. Rarely needed in contests, but it’s the standard answer for “approximate membership in little memory”.

Proof: the Bloom filter false-positive rate

Under the idealised assumption that each of the $k$ hash functions sends a key to a uniformly random bit (with replacement, independent of the others), the probability a specific bit is not set by one insertion is $1-\frac{1}{m}$; after $n$ insertions of $k$ bits each, the probability that bit is still 0 is ${\left(1-\frac{1}{m}\right)}^{kn}\approx e^{-kn/m}$. A query false-positives on a key not in the set exactly when all $k$ of its bits happen to already be set, which (treating the bits as independent, another idealisation) has probability ${\left(1-e^{-kn/m}\right)}^k$. Writing $p=e^{-kn/m}$, the false-positive rate is $(1-p{)}^k$; minimising over $k$ (treating $k$ as continuous, $p=e^{-kn/m}$) gives $\frac{d}{dk}[k\ln (1-e^{-kn/m})]=0$, which simplifies to $e^{-kn/m}=\frac{1}{2}$, i.e. $k=\frac{m}{n}\ln 2$ — at which point $p=\frac{1}{2}$ and the false-positive rate is $(\frac{1}{2}{)}^k=2^{-\frac{m}{n}\ln 2}\approx 0.6185^{m/n}$, about 0.6% at $m/n=10$. No false negative is possible since every bit a key sets stays set forever (the filter never clears a bit), so every one of a present key’s $k$ bits is still found set at query time. $■$

Which structure? (decision map)

Array with range queries
├─ static, idempotent (min, max, gcd)          -> sparse table, O(1)
├─ static, any associative op                  -> disjoint sparse table / sqrt tree
├─ static, k-th smallest / count <= x          -> wavelet matrix, persistent segment tree, merge sort tree
├─ point update, prefix sums                   -> Fenwick tree
├─ point update, any monoid                    -> segment tree (bottom-up)
├─ range update + range query                  -> lazy segment tree (or two Fenwicks for add/sum)
├─ chmin / chmax / historic values             -> segment tree beats
├─ insert / delete / reverse inside the array  -> implicit treap, splay
├─ operation that doesn't merge                -> sqrt decomposition, Mo
└─ all queries known in advance                -> offline sweep, Mo, CDQ, parallel binary search

Tree
├─ subtree queries                              -> Euler tour + Fenwick / segment tree
├─ path queries, static tree                    -> HLD, binary lifting (no updates)
├─ count / optimise over all paths              -> centroid decomposition
├─ queries on small vertex subsets              -> virtual tree
├─ subtree aggregates offline                   -> small-to-large (DSU on tree)
└─ link / cut online                            -> link-cut tree, Euler tour tree, top tree

Sets
├─ merge only                                   -> DSU (+ rollback / parity / weights)
├─ ordered with k-th / rank                     -> PBDS tree, Fenwick over values, treap
├─ min / max with deletions                     -> heap + lazy deletion, multiset
├─ meldable priority queues                     -> leftist / skew / pairing heap, small-to-large
├─ predecessor over integers in [0, 2^20)       -> 64-ary bit tree ("fast set")
└─ max XOR with an element / subset             -> binary trie / XOR basis

Strings                                          -> hashing, suffix array / automaton, Aho-Corasick, eertree
Geometry                                         -> Li Chao / CHT, KD-tree, sweep + BIT
Versions / history                               -> persistent segment tree / treap

Each structure has a note in this chapter or in Range Queries, Trees and Strings.

Container internals and pitfalls

Container	Key fact	Complexity
vector	doubling capacity amortizes growth (proof below)	access $O(1)$; unsorted search $O(n)$; sorted search $O(\log n)$; push/pop back $O(1)$ amortized; insert/erase elsewhere $O(n)$
singly/doubly linked list	no random access; $O(1)$ splice once you’re at the node	access/search $O(n)$; insert/delete at a known node $O(1)$ (doubly: also $O(1)$ to delete given only that node, since it knows its predecessor; singly needs a predecessor scan, $O(n)$)
stack (LIFO)	only the most recent element is reachable; array- or list-backed	push/pop/top all $O(1)$
queue (FIFO) / deque	queue needs a circular buffer or list to pop the front in $O(1)$ (a plain array shifting elements is $O(n)$); deque generalizes to both ends plus $O(1)$ random access	push/pop front and back $O(1)$; deque random access $O(1)$
unordered_map/set	chaining (this repo’s default) vs. open addressing (PBDS gp_hash_table, hand-rolled linear probing) are the two collision strategies	$O(1)$ average, $O(n)$ if hash-attacked (see Hashing above)
map/set	red-black tree; the two abilities a hash table lacks: sorted iteration and lower_bound/upper_bound	insert/erase/find/lower_bound $O(\log n)$; in-order traversal $O(n)$ total
priority_queue	binary heap = complete binary tree stored implicitly in an array; max-heap by default, pass greater<int> for min	push/pop $O(\log n)$; peek $O(1)$; build from $n$ elements $O(n)$ (proof: Heaps)
trie	each root-to-node path spells a shared prefix	insert/search a length-$L$ string: $O(L)$, independent of how many other strings are stored (binary trie over bits: Binary Trie)
DSU	union by size/rank + path compression	$O(\alpha (n))$ amortized (Tarjan) — full proofs, including the undo/persistent variants, in DSU, not reproduced here
bitset<N>	packs $N$ bits into machine words	AND/OR/XOR/count/shift over all $N$ bits: $O(N/64)$ instead of $O(N)$ (detail: Bitset)

Proof: push_back is $O(1)$ amortized under capacity doubling

Aggregate method: over $n$ calls to push_back, each call itself does $O(1)$ work besides any resize, contributing $O(n)$ total. A resize to capacity $2^k$ happens only when size reaches $2^{k-1}+1$ for successive $k$, and costs $O(2^{k-1})$ to copy the existing elements; since capacity at most doubles from one resize to the next, the resize sizes are bounded by a geometric sequence $1,2,4,\cdots \le n$, whose copying costs sum to $O(1+2+4+\cdots +n)=O(2n)=O(n)$. Total work for $n$ pushes is therefore $O(n)+O(n)=O(n)$, so the amortized cost per push_back is $O(n)/n=O(1)$. $■$

Iterator and reference invalidation — the classic silent-corruption source, worth a table of its own:

Container	Insert	Erase
vector	invalidates everything if capacity grows; otherwise only iterators/pointers from the insertion point onward	invalidates the erased element and everything after it
deque	invalidates all iterators; references/pointers survive unless the insert is in the middle	invalidates iterators to the erased element; references/pointers to others survive only if the erase is at an end
list / forward_list	never invalidates existing iterators/references/pointers	invalidates only the erased element’s own iterator
map / set / multimap / multiset	never invalidates existing iterators/references/pointers	invalidates only the erased element’s own iterator
unordered_map / unordered_set	invalidates all iterators on rehash (references/pointers survive); reserve upfront avoids it	invalidates only the erased element’s own iterator

The practical rule: vector and deque are the only containers where modifying the container can silently invalidate an iterator you’re still holding to a different element — the node-based containers (list, map/set, unordered_map/set) never do that, which is exactly why “erase while iterating” is safe for them (it = c.erase(it)) but needs care for vector/deque.

Array declaration choices:

Type	Size	Notes
int a[N] (global)	compile-time	zero-initialised, no stack limit, fastest
int a[N] (local)	compile-time	on the stack, ~1–8 MB limit, uninitialised
std::array<int, N>	compile-time	value semantics, usable as map keys
std::vector<int>	runtime	reserve, push_back amortised $O(1)$
vector<vector<int>>	2D runtime	rows can be ragged, slower than a flat array
flat vector<int>(n * m)	2D	index i * m + j, cache-friendly

Pitfalls:

Mistake	Fix
accumulate(..., 0) sums in int and overflows	seed with 0LL
memset(a, 1, sizeof a) sets bytes to 1, giving 16843009 per int, not 1	only safe for 0 and -1
clearing a big global array every test case, $O(N)$ per test	clear only the used prefix
vector<bool> is bit-packed: slow, not addressable	use vector<char> or bitset
out-of-bounds writes corrupt neighbours silently	compile with -D_GLIBCXX_DEBUG when debugging
std::list: one allocation per node, cache misses	prefer an array-based linked list (nxt[i]/prv[i])
missing sentinels at a linked list’s ends	forces null checks everywhere; add them
deleting a linked-list node twice corrupts it	track a deleted flag
std::deque’s per-element overhead in a hot loop (e.g. BFS)	a vector with a head index is faster
priority_queue with greater<> needs the full priority_queue<T, vector<T>, greater<T>>	the two-argument form doesn’t compile
front()/top() on an empty queue/stack	undefined behaviour — check empty() first

Classic pointer-chasing exercises worth having solved once: reverse a list (three pointers), detect a cycle (Tortoise and Hare), find the middle (slow/fast pointers), merge two sorted lists, intersect two lists (switch-heads trick). Doubly linked list + hash table is the standard LRU cache: the list keeps eviction order, the hash table gives $O(1)$ lookup of any node.

Stack applications, since “most recent unmatched thing” recurs constantly:

Problem	Idea
balanced brackets	push opens, pop on matching close
next/previous greater element	Monotonic Stack
largest rectangle in a histogram	monotonic stack of increasing heights
expression evaluation	two stacks (values, operators), or shunting-yard
iterative DFS	explicit stack instead of recursion
undo operations	stack of changes (rollback DSU)
stock span / days until warmer	monotonic stack
min-stack	store (value, min so far) pairs
queue with two stacks	amortised $O(1)$, aggregates any associative op