# Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$.

Is this tight ? Or alternately, is there a more restricted subclass for which you can get insertion time $P(n)/n$ (amortized or worst-case) even if $P(n) = O(n\log n)$ ? Here, $P(n)$ is the time to compute the result statically.

Consider range counting in one-dimensional intervals, in a comparison model of computation. That is, the data is a set $S$ of numbers, the query is an interval $[\ell,r]$, and the answer to a query is the size of $S\cap[\ell,r]$. Statically, you can solve it in $O(\log n)$ query time by storing $S$ as a sorted array and using binary search, in preprocessing time $P(n)=\Theta(n\log n)$. Dynamically, you can still solve it in $O(\log n)$ query time by using balanced binary search trees, with insertion time $O(\log n)=O(P(n)/n)$.