Ashwanth.K's blog

Union of Intervals using Segment Tree
By Ashwanth.K, history, 7 days ago, In English

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.

Hints

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:

  • Vote: I like it
  • +85
  • Vote: I do not like it

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem also uses 2-D segment tree in kind of same idea. Let me know if its a similar question.

→ Reply
»
7 days ago, # |
  Vote: I like it +39 Vote: I do not like it

This is well known in Croatia under the name Bradač trick.

→ Reply
  • »
    »
    6 days ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    so now we all not only gotta learn to read in chinese but in croatian too??

    → Reply
»
7 days ago, # |
  Vote: I like it +16 Vote: I do not like it

More problems using this trick: usaco guide

→ Reply
»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I usually code the merge like

if(left.minimum == right.minimum)
  return {left.minimum, left.frq + right.frq};
return min(left, right);
→ Reply
»
6 days ago, # |
  Vote: I like it -13 Vote: I do not like it

wow congrats

→ Reply