Interval Tree Data Structure: Range Searching, Overlap Queries, and Augmented Trees

An Interval Tree is an augmented balanced binary search tree designed for efficiently storing dynamic sets of intervals (such as [t_{\text{start}}, t_{\text{end}}] or [x_{\text{low}}, x_{\text{high}}]) and querying which intervals overlap with a given target point or range. While a naive linear scan across N intervals takes O(N) time per query, an Interval Tree answers stabbing queries and range overlap queries in O(\log N + k) time, where k is the number of reported overlapping intervals.

This guide details the structural invariants, augmentation mechanics (max_high subtrees), search algorithms, and real-world applications (computational geometry, calendar scheduling, genome sequence alignment, and memory virtual address mapping in operating system kernels).

1. Quick-Reference: Range Query Data Structures

+-----------------------------------------------------------------------------------------+
|                               RANGE QUERY DATA STRUCTURE COMPARISON                     |
+-----------------------------------------------------------------------------------------+
| Data Structure     | Primary Use Case     | Search Complexity   | Memory Overhead | Dynamic Mutation |
+--------------------+----------------------+---------------------+-----------------+------------------+
| Segment Tree       | Fixed range agg (sum)| O(log N)            | O(N) Array      | Moderate         |
| Interval Tree      | Dynamic interval sets| O(log N + k)        | O(N) Tree Nodes | Fast (O(log N))  |
| Range Tree (2D)    | Multi-dim points     | O(log^d N + k)      | O(N log^(d-1) N)| Slow             |
| R-Tree             | Spatial bounding box | O(log N) Avg        | O(N) Nodes      | Moderate         |
+-----------------------------------------------------------------------------------------+

2. Augmented Red-Black Interval Tree Architecture

An Interval Tree augments a standard balanced Binary Search Tree (such as a Red-Black Tree or AVL Tree):

1. Primary Key Ordering: Nodes are keyed by the interval's low endpoint (x.\text{low}), maintaining the standard binary search tree invariant.
2. Augmented Attribute: Each node x stores x.\text{max}, which is the maximum high endpoint found in the subtree rooted at x:

Interval Tree Node Structure with max_high Augmentation:
                   [ [16, 21] | max: 30 ]
                   /                    \
     [ [8, 9] | max: 23 ]          [ [25, 30] | max: 30 ]
     /                  \                  /
[ [5, 8] | max: 8 ]  [ [15, 23] | max: 23 ] [ [17, 19] | max: 19 ]

3. The Overlap Search Algorithm

To find an interval in the tree that overlaps with query interval i = [i.\text{low}, i.\text{high}]:

class IntervalNode:
    def __init__(self, low: int, high: int):
        self.low = low
        self.high = high
        self.max = high
        self.left = None
        self.right = None

def do_overlap(i1_low: int, i1_high: int, i2_low: int, i2_high: int) -> bool:
    return i1_low <= i2_high and i2_low <= i1_high

def interval_search(root: IntervalNode, q_low: int, q_high: int) -> IntervalNode:
    curr = root
    while curr is not None and not do_overlap(curr.low, curr.high, q_low, q_high):
        # If left subtree exists and its max is >= query low, overlap must be in left
        if curr.left is not None and curr.left.max >= q_low:
            curr = curr.left
        else:
            curr = curr.right
    return curr

The Search Correctness Proof

• If the algorithm traverses left, and curr.left.max >= q_low, either there is an overlap in the left subtree, or no overlapping interval exists anywhere in the entire tree.
• If the algorithm traverses right, there is guaranteed to be no overlap in the left subtree (because curr.left.max < q_low, so all high endpoints on the left are strictly below the query window).

4. Real-World Applications

1. Linux Kernel Virtual Memory Management: Tracks memory mapping ranges (vm_area_struct) using augmented interval trees to quickly detect memory overlap conflicts during mmap().
2. Computational Geometry: Solves the Windowing Problem (finding all geometric line segments that intersect a rectangular display viewport).
3. Genomic Sequence Alignment: Fast lookup of overlapping genomic features and sequencing reads against chromosome reference coordinates.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press (Chapter 14: Augmenting Data Structures).
2. de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer.
3. Linux Kernel Organization. (2024). Interval Trees in the Linux Kernel. Linux Kernel Documentation.