Hacker News new | past | comments | ask | show | jobs | submit login
Compact Fenwick trees for dynamic ranking and selection (2019) (arxiv.org)
39 points by luu 6 months ago | hide | past | favorite | 5 comments



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/


Looks good. Could benefit from some explanation of how to use x,y,z and how to compute the hash that apparently must be printed.


You 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.


> 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





Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: