The cell probe complexity of dynamic range counting

Abstract

In this paper we develop a new technique for proving lower bounds on the update time and query time of dynamic data structures in the cell probe model. With this technique, we prove the highest lower bound to date for any explicit problem, namely a lower bound of tq=Ω((lg n/lg(wtu))2). Here n is the number of update operations, w the cell size, tq the query time and tu the update time. In the most natural setting of cell size w=Θ(lg n), this gives a lower bound of tq=Ω((lg n/lg lg n)2) for any polylogarithmic update time. This bound is almost a quadratic improvement over the highest previous lower bound of Ω(lg n), due to Patrascu and Demaine [SICOMP'06].