Space efficient data structures for 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((lgnlglgn)2) worst-case time, and insertions and deletions in O((lgnlglgn)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×UU×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, [i1..i2][i1..i2], of indices and a range, [v1..v2][v1..v2], of values, count the number of entries of S[i1..i2]S[i1..i2] that store integers from [v1..v2][v1..v2].