We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving $O(\log n/\log \log n + k)$ optimal query time and $O(\log^{2/3+o(1)} n)$ update time (amortized) in the word RAM model, where $n$ is the number of data points and $k$ is the output size. This is the first improvement in over 10 years of Mortensen’s previous result [SIAM J. Comput., 2006], which has $O(\log^{7/8+\varepsilon} n)$ update time for an arbitrarily small constant $\varepsilon>0$.
In the case of 3-sided queries, our update time reduces to $O(\log^{1/2+\varepsilon} n)$, improving Wilkinson’s previous bound [ESA 2014] of $O(\log^{2/3+\varepsilon} n)$.