3 ms·
Compact Fenwick trees for dynamic ranking and selection (2019)
- mihaic 2y agoI 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/ https://csacademy.com/contest/archive/task/light-count/
- anonymoushn 2y agoLooks good. Could benefit from some explanation of how to use x,y,z and how to compute the hash that apparently must be printed.
- mihaic 2y agoYou can just start from the code snippets in C++/Java below the statement and implement the method stubs. We initially had an explanation on x,y,z, but in the end realized its safer to explicitly force people to copy/paste those pieces of code, to not accidentally mis-implement anything.
- froh 2y ago> 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
- wslh 2y agoMy two cents from 2012: https://blog.databigbang.com/esoteric-queue-scheduling-disciplines/ https://blog.databigbang.com/esoteric-queue-scheduling-disci...