[HN Gopher] Compact Fenwick trees for dynamic ranking and select...
___________________________________________________________________
Compact Fenwick trees for dynamic ranking and selection (2019)
Author : luu
Score : 30 points
Date : 2024-07-14 07:26 UTC (15 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| mihaic wrote:
| 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/
| anonymoushn wrote:
| 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.
| mihaic wrote:
| 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.
| froh wrote:
| > 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
___________________________________________________________________
(page generated 2024-07-14 23:02 UTC)