Minimal Indices for Successor Search

Sarel Cohen, Amos Fiat, Moshik Hershcovitch +1

We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from $O(n{w}^{4/5})$ bits to $O(n\log w)$…