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
andFrequency
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, SoN - 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)
This problem also uses 2-D segment tree in kind of same idea. Let me know if its a similar question.
This is well known in Croatia under the name Bradač trick.
so now we all not only gotta learn to read in chinese but in croatian too??
More problems using this trick: usaco guide
I usually code the merge like
wow congrats