An Efficient Data Structure for Range Selection Queries

Abstract

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