Space efficient data structures for dynamic orthogonal range counting

作者：He Meng^*; Munro J Ian

来源：Computational Geometry-Theory and Applications, 2014, 47(2): 268-281.

DOI：10.1016/j.comgeo.2013.08.007

• Succinct data structure
• Geometric data structure
• Dynamic data structure
• Orthogonal range counting
• Dynamic orthogonal range counting

We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers in the plane to support orthogonal range counting in O((lg n/lg lg n)(2))worst-case time, and insertions and deletions in O((lg n/lg lg n)(2)) amortized time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also consider the same problem for points on a U x U grid, and design the first succinct data structure for a dynamic integer sequence, S, to support range counting queries defined as follows: Given a range, [i(1)..i(2)] of indices and a range, [v(1)..v(2)], of values, count the number of entries of that store integers from [v(1)..v(2)].

• 出版日期2014-2