P.K.: Dynamic range selection in linear space

Abstract. Given a set S of n points in the plane, we consider the problem of answering range selection queries on S: that is, given an arbitrary x-range Q and an integer k> 0, return the k-th smallest y-coordinate from the set of points that have x-coordinates in Q. We present a linear space data structure that maintains a dynamic set of n points in the plane with real coordinates, and supports range selection queries in O((lgn / lg lgn)2) time, as well as insertions and deletions in O((lgn / lg lgn)2) amortized time. The space usage of this data structure is an Θ(lgn / lg lgn) factor improvement over the previous best result, while maintaining asymptotically matching query and update times. We also present the first succinct data structure that supports range selection queries on a dynamic array of n values drawn from a bounded universe.