An optimal dynamic interval stabbing-max data structure?

In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in ℝ^d, where each rectangle s ∈ S has a weight w(s) ∈ ℝ, so that the rectangle with the maximum weight containing a query point can be determined efficiently. We develop a linear-size structure for the one-dimensional version of the problem, the interval stabbing-max problem, that answers queries in worst-case O(log n) time and supports updates in amortized O(log n) time. Our structure works in the pointer-machine model of computation and utilizes many ingredients from recently developed external memory structures. Using standard techniques, our one-dimensional structure can be extended to higher dimensions, while paying a logarithmic factor in space, update time, and query time per dimension. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(log_B n) I/Os, where B is the disk block size.