Delete By Going Offline

Your structure supports add in $T(n)$ and has no delete. The whole operation sequence is known in advance. What does the segment-tree-over-time trick cost, and what does it forbid?

$O(T(n) \log n)$ total. Each element's lifetime decomposes into $O(\log n)$ nodes of a segment tree over the time axis, and a DFS adds on entry and rolls back on exit. It forbids nothing at all, and it accepts path compression, because the rollback stack restores the pointers exactly.

$O(T(n) \log n)$ total. Each element's lifetime decomposes into $O(\log n)$ nodes of a segment tree over the time axis, and a DFS adds on entry and rolls back on exit. It forbids online queries, and it forbids path compression, because every change must be undoable.

$O(T(n) \log^2 n)$ total. Each element's lifetime decomposes into $O(\log^2 n)$ nodes of a segment tree over the time axis, and a DFS adds on entry and rolls back on exit. It forbids online queries, and it forbids non-commutative merges, because the DFS visits lifetimes out of order.

$O(T(n) \sqrt{n})$ total. Each element's lifetime decomposes into $O(\sqrt{n})$ blocks of a decomposition over the time axis, and a DFS adds on entry and rolls back on exit. It forbids online queries, and it forbids more than $O(\sqrt{n})$ deletions, because every change must be undoable.