  We develop a new technique for proving cell-probe lower bounds on dynamic
data structures. This technique enables us to prove an amortized randomized
Omega(lg n) lower bound per operation for several data structural problems on n
elements, including partial sums, dynamic connectivity among disjoint paths (or
a forest or a graph), and several other dynamic graph problems (by simple
reductions). Such a lower bound breaks a long-standing barrier of Omega(lg n /
lglg n) for any dynamic language membership problem. It also establishes the
optimality of several existing data structures, such as Sleator and Tarjan's
dynamic trees. We also prove the first Omega(log_B n) lower bound in the
external-memory model without assumptions on the data structure (such as the
comparison model). Our lower bounds also give a query-update trade-off curve
matched, e.g., by several data structures for dynamic connectivity in graphs.
We also prove matching upper and lower bounds for partial sums when
parameterized by the word size and the maximum additive change in an update.
