Space Efficient Data Structures for Dynamic Orthogonal Range Counting

Abstract. We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers on the plane to support orthogonal range counting, as well as insertions and deletions, in O( ( lgn lg lgn)2) time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also obtain two other new results by considering the same problem for points on a U × U grid, and by designing the first succinct data structures for a dynamic integer sequence to support range counting.