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.

Initial Thought Process

• Since these operations are range addition and range deletion, one could think of maintaining a Lazy segment tree to perform these.

• But finding the union of the segments is hard to calculate, especially during a removal operation of a segment.

Solution:

• We can modify this problem to count the number of points that are not included by any segments.
• The answer to the problem is Union of segments = N - Number of Non-Included points.
• We can maintain a lazy segment tree to store the Minimum Element and Frequency of this minimum element.
• The updates of the lazy segment tree is range addition (subtraction is same as addition of negative number).

After a range updation, the minimum element can be easily recalculated as minimum += addOperation.
And Left and Right nodes of segment tree can be easily merged as follows:

   node.minimum  = min(left.minimum , right.minimum);
   node.frq = 0;
   if(node.minimum == left.minimum) node.frq += left.frq;
   if(node.minimum == right.minimum) node.frq += right.frq;

So the node.frq gives me the frequency of minimum element present in the segment tree.

• If the minimum element is non zero, this shows that none of nodes are 0, (all points are included by the segments).
• If the minimum element is zero, then node.frq reveals the count of 0s present in the number line, So N - node.frq gives me the union length of all the segments.

• Since all elements are always $$$\ge 0$$$ (due to the removal operation of an existing interval), this idea works.

Practice Problems:

• CSES Area of Rectangles (Sliding window + Segment Tree)

• ICPC Asia West finals problem (Fix L pointer, Segment Tree)