Advanced Structures Reference

Choose by the operation contract

Need	Candidate	Boundary to check
Ordered lookup, rank and selection	Augmented AVL map	Unique keys, replacement policy, deletion and size maintenance
Incremental undirected connectivity	Union by size with path compression	Initialization, redundant edges, no paths or arbitrary deletion
Destructive melding of priority queues	Binomial heap	Donor ownership, duplicate keys, no implicit stable handles
Append sequence	Geometrically growing array	Cost unit, resize latency, initial state and peak storage
Point addition and range sum	Fenwick tree	Half-open indexing and additive inverses
Range assignment/addition and sum	Lazy segment tree	Tag chronology, segment length and identity
Branching historical point updates	Persistent sum tree	Immutable sharing, retained roots and historical membership
Negative membership shortcut	Bloom filter plus exact store	Covered population, stable hashing, no unsafe clearing

Read the operation and resource contracts before adapting code. The reading guide maps local books to questions, and resources records primary references.

Proof and verification cards

For each chosen structure record its state invariant, legal operations, ownership, input domain, output contract, worst-call bound, sequence/expected bound, and space model. Add one minimal failing sequence and one independent model check. Separate a proved theorem from a measured observation and an untested hypothesis.

The practice key contains derivations; the assessment key is intended for review after an independent attempt. Use the mistake clinic to repair actual misconceptions rather than collect a quota of mistakes.