Project: audit sparse readings and task constraints

Acceptance trace

Assign reading 19 at coordinate 47 and 26 at a far coordinate, then replace the first reading with 52. The near range sums to 52 and the whole range to 78; clearing coordinate 47 returns the near sum to zero. For latency sequence 61, 19, 47, 19, 83, 26, 52, count readings below 47 in [1, 6) and select sorted ordinal 2 there. Expect three and 26. Build parity constraints A-19 different A-47, then A-47 different A-61. A-19 and A-61 must be the same; reject a contradictory different request. Reverse task positions [1, 4), insert T-26 at position 2, and confirm T-19, T-83, T-26, T-61, T-47.

Expected output

near=52 whole=78 cleared=0
below=3 ordinal-2=26
A-19/A-61=same contradiction=rejected
T-19 T-83 T-26 T-61 T-47

Cost and boundary review

The sparse tree pays O(log U) time per point change or range sum over logical span U, while retaining paths that once held values. The wavelet tree builds O(N log sigma) prefix entries and answers fixed-sequence subarray count or select in O(log sigma) time. Parity union-find handles additions in amortized O(alpha(N)) time but cannot remove constraints. An implicit treap gives expected O(log N) positional edits and reversals, while a complete snapshot costs O(N). Explain why none of these indexes should be described as a concurrent or durable production store without separate synchronization and persistence work.

Common Mistakes

• Do not add a replacement meter reading on top of the previous value.
• Do not use a wavelet prefix from the parent as a child-local position.
• Do not accept a conflicting parity edge within an existing component.
• Do not read an implicit treap subtree without pushing its reversal flag.

Connected lessons

• Sparse coordinate segment tree: allocate only visited paths
• Wavelet tree: subarray counts and order statistics
• Parity disjoint set: maintain same-or-different constraints
• Implicit treap: edit positions and reverse a range
• Projects
• Quizzes
• Data Structures