COURSE II · REGIONAL · VERSION 2
Disjoint sets and range queries
Measurable outcome: Implement DSU and a Fenwick tree from memory, explain their invariants, and select the right structure under contest pressure.
Concept checklist
- Path compression and union by size
- Component invariants and amortized complexity
- Prefix sums as a bridge to Fenwick trees
- Point updates, prefix queries, and coordinate compression
Implementation lab
- Write DSU with find, unite, same, and size operations.
- Write a 1-indexed Fenwick tree with add and prefix-sum operations.
- Create randomized tests against a slow reference implementation.
Mapped problems
Exit criteria
- Explain the key invariant without notes.
- Reimplement the core technique in one sitting.
- Solve two mapped tasks without editorial help.
- Record one mistake and the test that exposes it.