I recently came across the idea of using a Segment Tree to solve the union of intervals problem. I noticed that a few problems utilize this idea, and I would like to discuss the same.

Problem Statement:
You are given $$$N$$$ $$$(1 \le N \le 10^5)$$$, the number of points in a coordinate system, and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ queries, where each query is of the form $$$[l_i , r_i]$$$ $$$(1 \le l_i \le r_i \le N)$$$.

• For each query, if the line segment $$$[l_i, r_i]$$$ is not already present, you need to include this segment.
• otherwise, you need to remove this line segment.

After processing each query, report the total union length of all the active line segments.

Example:

For $$$N = 8, $$$ $$$Q = 4$$$
Query 1) ADD [3,4]

Union of segments is 1 unit.

Query 2) ADD [5,6]

Union of segments is 2 unit.

Query 3) ADD [3,6]

Union of segments is 3 unit.

Query 4) REMOVE [3,6]

Union of segments is 2 unit.