Project: audit four range-query workloads

Acceptance trace

Use capacities 23, 47, 19, 61, 38, 52, 29; replace position three with 74 and require 230 over [1, 6). Use readings 41, 18, 41, 73, 26, 55, 12 and require three values at most 41 over [1, 6). On the original capacity snapshot, require 217 over [1, 6), 61 over [3, 4), and zero over [2, 2). Insert tariffs 7x+13, 4x+49, and 9x-11 over integer x from zero through 80; require minimums 34 at five and 189 at 35. These checks expose both endpoint convention and the distinction between a mutable index and a frozen snapshot.

Expected output

corrected-sum=230 threshold-count=3 frozen-sum=217
tariff-at-5=34 tariff-at-35=189

Boundary and cost review

Try an empty array, empty intervals, duplicate threshold values, a negative capacity correction, an empty tariff book, and a query just outside the declared quantity domain. Then state which edits require rebuilding each immutable index. Compare query-heavy and update-heavy workloads before choosing a structure. Measure memory as well as steps: the two static tables replicate values across logarithmic levels, while the block index keeps the underlying array plus block totals. Document whether the workload truly needs the general associative table when a prefix sum would be cheaper.

Common Mistakes

• Do not include the stop position in a half-open query.
• Do not count a threshold equal to the bound as excluded.
• Do not use overlapping sparse-table intervals for addition.
• Do not query an empty tariff book or outside its domain.

Connected lessons

• Square-root blocks: update one capacity and sum a range
• Merge-sort trees: count readings below a threshold in one interval
• Disjoint sparse tables: immutable sums with constant-time queries
• Li Chao trees: minimum linear tariff at a chosen quantity
• Projects
• Quizzes
• Data Structures