The first data structure to provide time , , and operations was proposed by van Emde Boas and has since become known as the van Emde Boas (or stratified) tree . The original van Emde Boas structure had size , so was impractical for large integers.
The and data structures were discovered by Willard . The structure is very closely related to van Emde Boas trees. One view of this is that the hash tables in an replace arrays in a van Emde Boas tree. That is, instead of storing the hash table , a van Emde Boas tree stores an array of length .
Another structure for storing integers is Fredman and Willard's fusion trees . This structure can store -bit integers in space so that the operation runs in time. By using a fusion tree when and a when one obtains an space data structure that can implement the operation in time. Recent lower-bound results of Ptracu and Thorup  show that these results are more-or-less optimal, at least for structures that use only space.
Hint: Each node in your data structure should store a hash table that is indexed by character values.