Explanation:
- An **Interval Tree** is a balanced binary search tree used to store intervals. It allows querying for all intervals that overlap with a given interval.
-
- It is particularly useful in applications like scheduling, computational geometry, and range queries.
-
-
Steps:
- Each node in the interval tree stores an interval and the maximum value of the interval’s end point in its subtree.
- Insert and Query operations are similar to binary search trees with added logic to handle intervals.
-
Time Complexity:
- Insertion: O(log n)
- Query: O(log n + k), where k is the number of intervals that overlap with the query interval.