First of all this technique isn't anything new, it's a fairly well known one but I couldn't find any resources 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: Given a graph 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 time

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(logQ)$$$ 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(logN)$$$).

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

At a 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(QlogQlogN)$$$.

How is this useful?

You may be wondering by this point how this is useful at all since Dynamic Conectivity can be solved with Link-Cut trees online in $$$O(QlogN)$$$ but 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 where addition and deletion of pretty much anything to any structure but we need to be able to handle addition and most importantly rollbacks in a good time complexity.