Project: audit incident flags, depot paths, and sorted runs

Acceptance trace

Place active flags at timeline positions 19, 47, and 61. Rank at stop 48 must be 2; selecting ordinal 1 must locate position 47. Query the D-52 to D-83 path with depot weights 17, 11, 7, 13, and 23 along that route, obtaining 71. Replace D-19's weight 7 with 29, and require 93 for the same route but 47 for D-61 to D-52. Flush A-19=west and A-47=north; then flush A-19=east and a deletion marker for A-47. Verify the visible results before and after full compaction.

Expected output

rank1(48)=2 select1(1)=47
path-before=71 path-after=93 alternate=47
A-19=east A-47=missing runs-before=2 runs-after=1

Cost and boundary review

Rank is O(1) over a bounded packed word, while this select implementation searches the word-prefix array. A point weight update is O(log N) and a heavy-light path sum is O(log² N). A missing-key sorted-run lookup may search every run, and full compaction rewrites all surviving keys. Reject invalid ordinals, malformed trees, and unsupported value types in the test suite. The bitmap and tree topology cannot be edited by their shown APIs. The sorted-run program is only an in-memory model; writing these tuples to disk without a journal and recovery protocol would not make it crash safe.

Common Mistakes

• Do not include the stop position in a prefix rank.
• Do not count a chain junction twice.
• Do not read an older run past a newer deletion marker.
• Do not discard a marker while older runs can still supply the deleted key.

Connected lessons

• Bitvector rank and select: count and locate set bits
• Heavy-light decomposition: sum weights along a tree path
• Sorted runs and tombstones: model an LSM read path
• Projects
• Quizzes
• Data Structures