Discussion on Data Structures for Integers

Additional notes

The first data structure to provide $O(\log w)$ time add(x), remove(x), and find(x) operations was proposed by van Emde Boas and has since become known as the van Emde BoasP. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett., 6(3):80–82, 1977. (or stratified) tree. The original van Emde Boas structure had size $2^w$, making it impractical for large integers.

The XFastTrie and YFastTrie data structures were discovered by WillardD. E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Inf. Process. Lett., 17(2):81–84, 1983.. The XFastTrie structure is closely related to van Emde Boas trees; for instance, the hash tables in an XFastTrie replace arrays in a van Emde Boas tree. That is, instead of storing the hash table $t[i]$, a van Emde Boas tree stores an array of length $2^i$.