Log-logarithmic worst-case range queries are possible in space Θ(N)

Let S denote a set of N records whose keys are distinct nonnegative integers less than some initially specified bound M. This paper introduces a new data structure, called the y-fast trie, which uses Θ(N) space and Θ(log log M) time for range queries on a random access machine. We will also define a simpler but less efficient structure, called the x-fast trie.