Implement an Interval Tree in JavaScript

You are tasked with implementing a data structure called an Interval Tree in JavaScript. This tree will efficiently store and query overlapping intervals. Interval trees are particularly useful in computational geometry, scheduling systems, and genomic analysis where you need to quickly find all intervals that contain a given point or overlap with a given interval.

Problem Description

Your goal is to create a JavaScript class, IntervalTree, that can store a collection of intervals and perform efficient range queries. An interval is defined by a start and end point (inclusive).

Key Requirements:

1. Interval Representation: Each interval should be represented as an object or array with start and end properties (or indices). For this challenge, assume intervals are [start, end].
2. Construction: The IntervalTree should have a constructor that accepts an array of intervals and builds the tree.
3. Insertion: A method to add new intervals to the tree after it has been constructed.
4. Querying for Overlapping Intervals: A method that takes a query interval [queryStart, queryEnd] and returns an array of all intervals in the tree that overlap with the query interval. Two intervals [a, b] and [c, d] overlap if max(a, c) <= min(b, d).
5. Querying for Intervals Containing a Point: A method that takes a point p and returns an array of all intervals in the tree that contain p (i.e., start <= p <= end).

Expected Behavior:

• The tree should be constructed optimally for the given intervals.
• Insertion should maintain the tree's structure and efficiency.
• Queries for overlapping intervals and point containment should return correct results and be performed efficiently.

Edge Cases:

• Empty interval list during construction.
• Querying with an empty tree.
• Intervals with zero length (e.g., [5, 5]).
• Query intervals or points that lie exactly on interval boundaries.
• Duplicate intervals.

Examples

Example 1:

Input intervals: [[15, 20], [10, 30], [17, 19], [5, 20], [12, 15], [30, 40]]

// After building the tree:
// Query for intervals overlapping with [14, 16]

Output: [[15, 20], [10, 30], [5, 20], [12, 15]]
Explanation:
- [15, 20] overlaps with [14, 16] because 15 <= 16 and 14 <= 20.
- [10, 30] overlaps with [14, 16] because 10 <= 16 and 14 <= 30.
- [5, 20] overlaps with [14, 16] because 5 <= 16 and 14 <= 20.
- [12, 15] overlaps with [14, 16] because 12 <= 16 and 14 <= 15.
- [17, 19] does not overlap because max(17, 14) = 17 > min(19, 16) = 16.
- [30, 40] does not overlap because max(30, 14) = 30 > min(40, 16) = 16.

Example 2:

Input intervals: [[1, 5], [2, 6], [8, 10], [15, 18]]

// After building the tree:
// Query for intervals containing point 4

Output: [[1, 5], [2, 6]]
Explanation:
- [1, 5] contains 4 because 1 <= 4 <= 5.
- [2, 6] contains 4 because 2 <= 4 <= 6.
- [8, 10] does not contain 4.
- [15, 18] does not contain 4.

Example 3: (Insertion and Overlap Query)

Input intervals: [[1, 10]]
// Tree is initialized with [[1, 10]]

// Insert interval: [5, 15]

// Query for intervals overlapping with [8, 12]

Output: [[1, 10], [5, 15]]
Explanation:
After insertion, the tree contains [1, 10] and [5, 15].
- [1, 10] overlaps with [8, 12].
- [5, 15] overlaps with [8, 12].

Constraints

• The number of intervals can be between 0 and 10^5.
• Interval start and end points will be integers between -10^9 and 10^9.
• Query intervals and points will also be within this integer range.
• The implementation should aim for logarithmic time complexity for insertion and query operations (e.g., O(log N + K) where N is the number of intervals and K is the number of reported overlapping intervals).

Notes

• An interval tree is typically built on a balanced binary search tree. Each node in the tree stores an interval and also the "center" point around which the subtree is partitioned. Additionally, each node stores the maximum endpoint of all intervals in its subtree. This maximum endpoint is crucial for pruning the search during queries.
• Consider how you will handle the recursive construction and query logic.
• The choice of the median point for partitioning is important for balancing the tree.
• Think about how to efficiently combine results from recursive calls.
• You may want to implement helper methods for node creation and recursive traversal.