Interval Tree Template

Problem Statement

Given a static set of n intervals, answer a stream of point queries: for a given point q, return every interval that contains q. The goal is O(log n + k) per query, where k is the size of the answer.

Input

• A set of intervals [[start, end], …] known up front.
• A sequence of integer point queries.

intervals = [[1,5],[3,7],[6,10],[8,12]]
queries   = [4, 7, 11]

Output

For each query, the intervals that contain the query point.

query 4  → [[1,5],[3,7]]
query 7  → [[3,7],[6,10]]
query 11 → [[8,12]]

Constraints

• Intervals are known in advance (static tree).
• n up to a few million in practice; queries typically q ≤ n.
• Conceptual pattern — rarely coded from scratch in interviews.

Intuition

Choose a center point (typically the median of all endpoints). Intervals are partitioned into three buckets:

• Crossing the center — stored at this node, maintained sorted by both start and end (for fast pruning in either direction).
• Entirely left — recurse into the left subtree.
• Entirely right — recurse into the right subtree.

To query a point q:

1. Inspect the node’s crossing intervals — those containing q are answers.
2. If q < center, recurse left; else recurse right. Only one side can match, so the recursion depth is O(log n).

Total cost: O(log n) to descend + O(k) to report hits.

                    ┌──────────────┐
                    │ center = m   │
                    │ crossing:    │
                    │  intervals   │
                    │  spanning m  │
                    └───┬──────┬───┘
                        │      │
                q < m   │      │   q > m
                        ▼      ▼
                     left    right
                    subtree  subtree

Solution

query(node, q):
  if node is None: return []
  hits = [ivl for ivl in node.crossing if ivl contains q]
  if q < node.center:
    return hits + query(node.left, q)
  else:
    return hits + query(node.right, q)

Complexity

Edge Case Thinking