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 UxU 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 S[i"1..i"2] that store integers from [v"1..v"2].