Specialized Structures
Union-Find, sparse tables, Bloom filters, caches and skip lists.
Tracks a partition of elements into disjoint sets with near-constant-time find and union, using path compression and union by rank.
A precomputed table of answers over power-of-two-length blocks that answers idempotent range queries (min, max, gcd) in O(1) after O(n log n) build, for static arrays.
A bit array plus k hash functions that answers "possibly in the set" or "definitely not" in O(k) with a tiny memory footprint and no false negatives.
A fixed-capacity key-value store that evicts the least recently used entry, with O(1) get and put via a hash map plus a doubly linked list.
A fixed-capacity cache that evicts the entry with the lowest access count (ties broken by least recent), in O(1) using a map of frequency buckets.
A sorted linked list with randomised express lanes stacked on top, giving expected O(log n) search, insert, and delete without any rebalancing.