First of all, this technique isn't anything new, it's a fairly well known one, but I couldn't find any resources on this topic other than [this comment](https://mirror.codeforces.com/blog/entry/15296?#comment-203606) 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 graphA graph is given with N$N$ nodes and Q$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 time1$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.↵
↵
Atathe 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 \logQ 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 with Link-Cut trees online in $O(Q \log N)$ but i.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 whereith 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. ↵
↵
. 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 [user:EntityPlantt,2026-04-03] for using his grammar police abilities for once to not ragebait me and instead help me fix my terrible grammar.↵
↵
↵
↵
↵
↵
↵
With that being said, let's begin with the blog.↵
↵
The problem↵
==================↵
Lets consider the following problem:↵
↵
- 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
↵
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
↵
At each node, we add all the edges in the node to the DSU, recurse downwards, and then rollback.↵
↵
At
↵
This way we will handle everything offline in $O(Q \log
↵
How is this useful?↵
==================↵
↵
You may be wondering by this point how this is useful at all since Dynamic Connectivity can be solved with Link-Cut trees online in $O(Q \log N)$
↵
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 w
↵
↵
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 [user:EntityPlantt,2026-04-03] for using his grammar police abilities for once to not ragebait me and instead help me fix my terrible grammar.↵
↵
↵
↵
↵
↵
