We propose RPST, a randomized data. structure for the 11/2-dimensional range query problem, based on a version of, Skip Lists, as an alternative to solutions that use. deterministic height balanced trees. Our scheme exhibits, with high probability, logarithmic, output-sensitive search time, expected logarithmic update time, expected constant reconstruction time and linear space overhead with high probability.
(EN)
Πανεπιστήμιο Θεσσαλίας
