First of all, this technique isn't anything new, it's a fairly known one, but I couldn't find any resources on this topic other than this comment which is somewhat hard to find, so I decided to write a full blog.

With that being said, let's begin with the blog.

The problem

Lets consider the following problem: A graph is given with $$$N$$$ nodes and $$$Q$$$ queries. Each query is one of the following:

• Add edge $$$(u,v)$$$
• Remove edge $$$(u,v)$$$
• Query the number of connected components in the graph

The timeline

Lets imagine a timeline, from time $$$1$$$ to time $$$Q$$$, at each moment either some edge gets added, removed, or a query gets asked.

Now the main idea of this technique is instead of dealing with deletions, for each edge we determine some intervals during which it exists. Namely if edge $$$(u, v)$$$ gets added at time $$$A$$$ and then later removed at time $$$B$$$ then that edge will obviously exist in the time frame $$$[A, B)$$$.

The Segment Tree on time

Now we've turned the problem into a range update problem, which suggests using a segment tree. We build a segment tree over the timeline. For each node, we store a list of edges that are active throughout the segment represented by that node.

Each interval gets decomposed into $$$O( \log Q)$$$ segments in the tree, and for each of those segments, we simply add the corresponding edge to the node.

After building the tree, we will run a DFS on it while maintaining a DSU with rollbacks (this is a well-known structure that can handle operations in $$$O(\log N)$$$).

At each node, we add all the edges in the node to the DSU, recurse downwards, and then rollback.

At the leaves, if the time corresponds to a query we can easily answer it since our DSU is already built.

This way we will handle everything offline in $$$O(Q \log Q \log N)$$$.

How is this useful?

You may be wondering by this point how this is useful at all since Dynamic Connectivity can be solved both online and offline in a better time complexity.It turns out this technique can be generalized.

Notice that the only part specific to the problem that we used in our solution is the Rollback DSU. So this technique can be applied in any problem with addition and deletion of pretty much anything to any structure. The only condition is that we need to be able to handle addition, and most importantly, rollbacks in a good time complexity.

In return for writing this amazing blog I am asking you to link any problems that can be solved with this technique in the comments.

Big thanks to EntityPlantt for using his grammar police abilities for once to not ragebait me and instead help me fix my terrible grammar.