Problems for talk on "Dynamic Range Reporting in One Dimension"

1) van Emde Boas: Most hash tables work on keys of a fixed number of 
bits, whereas the vEB data structure needs to hash variable-length 
prefixes of keys.
Explain how to convert variable length keys of length at most w into 
distinct fixed length keys of length 2w (or better).

2) New data structure: Argue that the query time for FindAny(a,b)
can be improved slightly from O(log log w) to O(log log (w-lcp(a,b))),
where lcp(a,b) is the length of the longest common prefix of a and b.
Hint: Argue that only the O(log(w-lcp(a,b))) tries of lowest order need 
to be searched.

3) Extra credit (hard): Improve the answer from the last question to 
expected time O(log log log(b-a)).