An Efficient Data Structure for Range Selection Queries

Xiaodong Wang

Indonesian Journal of Electrical Engineering and Computer Science
Vol 12, No 3: March 2014

In this work, we consider the problem of building an efficient data structure for range selection queries. While there are several theoretical solutions to the problem, only a few have been tried out, and there is little idea on how the others would perform. The computation model used in this paper is the RAM model with word-size $\Theta(\log n)$. Our data structure is a practical linear space data structure that supports range selection queries in $O(\log n)$ time with $O(n\log n)$ preprocessing time. DOI : http://dx.doi.org/10.11591/telkomnika.v12i3.3629