In 1979, Bentley introduced one of the first general techniques for turning a static data structure into a data structure that supports insertions. This general technique can be applied to any query problem that is “decomposable”: Assume the set $S$ of objects is partitioned into two subsets $A$ and $B$. A query problem on $S$ is decomposable, if the answer to the query on $S$ can be obtained in $O(1)$ time from the answer to the query on $A$ and the answer to the query on $B$.

In this talk, I will present Bentley's construction. I will also present a more general construction, that supports “semi-online” updates: Insertions are fully on-line, but with each inserted object, the time of deletion is specified. This construction is originally due to Dobkin and Suri (1989), and was simplified by the speaker at the 2nd CCCG, which was held in Ottawa in 1990.