  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 $t_q=\Omega((\lg n/\lg(wt_u))^2)$. Here $n$ is
the number of update operations, $w$ the cell size, $t_q$ the query time and
$t_u$ the update time. In the most natural setting of cell size $w=\Theta(\lg
n)$, this gives a lower bound of $t_q=\Omega((\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 $\Omega(\lg n)$, due to P\v{a}tra\c{s}cu
and Demaine [SICOMP'06].
  We prove the lower bound for the fundamental problem of weighted orthogonal
range counting. In this problem, we are to support insertions of
two-dimensional points, each assigned a $\Theta(\lg n)$-bit integer weight. A
query to this problem is specified by a point $q=(x,y)$, and the goal is to
report the sum of the weights assigned to the points dominated by $q$, where a
point $(x',y')$ is dominated by $q$ if $x' \leq x$ and $y' \leq y$. In addition
to being the highest cell probe lower bound to date, the lower bound is also
tight for data structures with update time $t_u = \Omega(\lg^{2+\eps}n)$, where
$\eps>0$ is an arbitrarily small constant.
