Range selection and predecessor queries in data aware space and time

On a given vector X=〈x1,x2,…,xn〉 of integers, the range selection (i,j,k) query is finding the k-th smallest integer in 〈xi,xi+1,…,xj〉 for any (i,j,k) such that 1≤i≤j≤n, and 1≤k≤j−i+1. Previous studies on the problem proposed data structures that occupied additional O(n⋅log⁡n) bits of space over the X itself that answer the queries in logarithmic time. In this study, we replace X and encode all integers in it via a single wavelet tree by using S=n⋅log⁡u+∑log⁡xi+o(n⋅log⁡u+∑log⁡xi) bits, where u is the number of distinct ⌊log⁡xi⌋ values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when xi>u, the space used for xi in the proposed data structure is less than the Elias-δ coding of xi. Besides data-aware coding of X, the range selection is performed in O(log⁡u+log⁡x′) time where x′ is the k-th smallest integer in the queried range. This result is adaptive and achieves the range selection regardless of the size of X, and the time-complexity depends on the answer itself. Additionally, we can answer range predecessor queries (i,j,x′): return the largest element y≤x′ in 〈xi,xi+1,…,xj〉, in O(log⁡u+log⁡x′) time. In summary, to the best of our knowledge, we present the first algorithms using data-aware space and time for the general range selection and predecessor problems.