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.
