I just want to add that succinct data structures are reasonably straightforward to develop when there's an actual requirement, so I would have wanted to see some better benchmarking numbers here.
I had pretty much this same task as the second hardest challenge in a 2-hour competitive programming contest, and plenty of people came up with the solution on the spot. Try an implementation yourself if you're up for it here: https://csacademy.com/contest/archive/task/light-count/
> Our aim is to use our variants to implement an efficient dynamic bit vector: our structure is able to perform updates, ranking and selection in logarithmic time, with a space overhead in the order of a few percents,
large bit vectors as in 10^6..10^10 bit bit veczors
mihaic ·107 days ago
I had pretty much this same task as the second hardest challenge in a 2-hour competitive programming contest, and plenty of people came up with the solution on the spot. Try an implementation yourself if you're up for it here: https://csacademy.com/contest/archive/task/light-count/
Show replies
froh ·106 days ago
large bit vectors as in 10^6..10^10 bit bit veczors
wslh ·106 days ago