The Interval Tree

An interval tree is a specialized ordered tree data structure designed to hold intervals. It allows efficient retrieval of all intervals that overlap with any given point or interval. While standard search trees map individual discrete keys to specific values, an interval tree maps a continuous range of values, defined by a lower and upper bound, to a specific node.^[28] This capability is required in domains where data represents durations, physical dimensions, or ranges of memory addresses.

The core problem the interval tree solves is the one-dimensional overlap query. Given a dynamic set of intervals, finding which ones intersect a query point (a stabbing query) or a query interval (a range query) takes linear time if the intervals are stored in an unsorted list. By organizing the intervals hierarchically, an interval tree reduces the query time to logarithmic bounds, specifically O(log N + k) where N is the total number of intervals and k is the number of overlapping intervals returned. The structure requires O(N) space, making it optimally efficient in memory consumption compared to alternative spatial data structures.

Two primary variants of the interval tree exist in computer science literature. The centered interval tree, originally developed for computational geometry, divides intervals based on a central point. The augmented interval tree, popularized by standard algorithmic textbooks, modifies a standard balanced binary search tree by adding a single scalar value to each node. The centered interval tree has O(log N + k) query time, while the augmented interval tree has O(k log N) query time, though they differ in implementation complexity and suitability for dynamic insertions and deletions.

Definition and Problem Statement

An interval is defined as a contiguous range of values [low, high] over a totally ordered domain, such that low <= high. The domain is typically the set of real numbers, integers, or timestamps. Intervals can be closed (inclusive of endpoints), open (exclusive of endpoints), or half-open. For the purposes of standard interval tree logic, they are generally treated as closed ranges where the endpoints are inclusive. A zero-length interval where low == high is treated as a single point.

Two intervals [a, b] and [c, d] overlap if and only if a <= d and c <= b. This mathematical definition of overlap is a simplification of the broader temporal logic framework known as Allen's interval algebra, introduced by James F. Allen in 1983 Maintaining knowledge about temporal intervals^[1]. Allen defined thirteen distinct relations between two intervals, such as precedes, meets, overlaps, starts, during, and finishes. While the standard interval tree is optimized for the general intersects relation, the underlying tree structure can be modified to filter for any of Allen's specific relations by adding secondary checks during the traversal phase.

In database systems, computational geometry, and bioinformatics, applications frequently need to maintain a set of such intervals and answer two specific types of queries. The first is a stabbing query, which provides a single point x and requests all intervals [low, high] in the set where low <= x <= high. The second is an interval overlap query, which provides a query interval [q_low, q_high] and requests all intervals in the set that intersect it.

A naive approach stores the intervals in a simple array or linked list. Inserting a new interval takes O(1) time, but querying requires scanning the entire collection, resulting in O(N) time complexity. If the dataset is static, sorting the intervals by their starting points allows a binary search to find the first potential overlap in O(log N) time. However, long-spanning intervals that start early but extend far to the right force the search algorithm to scan large portions of the array, degrading the worst-case query time back to O(N). For example, an interval [0, 1000] would start at the beginning of a sorted array but overlap with a query point at 999. The interval tree guarantees O(log N + k) query time by structurally bounding the search space, ensuring that the algorithm only visits nodes that either contain an overlapping interval or lead to one.

Mechanism and Implementation

The two dominant forms of the interval tree operate on different structural principles. Both achieve the same theoretical efficiency but are suited to different operational constraints.

The Centered Interval Tree

The centered interval tree is a static or semi-dynamic structure that recursively divides the set of intervals.^[28] To construct it, the algorithm first extracts all the endpoints (both low and high) from the dataset. It then determines the median point x_center of these endpoints. Finding the median can be done in O(N log N) time by sorting the endpoints, or in O(N) time using a selection algorithm like median-of-medians.

Once x_center is established, the intervals are partitioned into three distinct sets: intervals completely to the left of x_center (where high < x_center), intervals completely to the right of x_center (where low > x_center), and intervals that contain x_center (where low <= x_center <= high).

The intervals that contain x_center are stored in the current node using two separate sorted lists. One list is sorted by the low endpoints in ascending order, and the other is sorted by the high endpoints in descending order. The algorithm then recursively constructs a left child tree for the left-side intervals and a right child tree for the right-side intervals. Because the intervals are divided roughly in half at each step, the maximum depth of the tree is strictly bounded to O(log N). The total construction time is O(N log N).

Consider a concrete numerical example with a dataset of five intervals: [1, 5], [2, 8], [4, 6], [7, 10], and [9, 12]. The endpoints are 1, 2, 4, 5, 6, 7, 8, 9, 10, 12. The median of these endpoints is 6, so the center point x_center is set to 6. The intervals are partitioned such that the left set contains [1, 5], the right set contains [7, 10] and [9, 12], and the center set contains [2, 8] and [4, 6]. The center node stores [2, 8] and [4, 6]. The left list sorted by low is [2, 8], [4, 6]. The right list sorted by high is [2, 8], [4, 6]. The algorithm then recursively processes the left and right sets.

To answer a stabbing query for a point q, the algorithm compares q to x_center. If q < x_center, the algorithm scans the node's list sorted by low endpoints. It reports intervals until it encounters one whose low is greater than q. Because the list is sorted, all subsequent intervals will also have a low greater than q, allowing the scan to terminate early. It then recursively searches the left child. If q > x_center, the algorithm scans the list sorted by high endpoints, reporting intervals until it encounters one whose high is less than q, and then recursively searches the right child. If q == x_center, all intervals in the center set overlap q, so they are all reported, and no further recursion is needed.

This structure guarantees O(N) space because each interval is stored exactly once in the center set of exactly one node. The tree height is bounded to O(log N), ensuring the O(log N + k) query time.

The Augmented Search Tree

The augmented interval tree is highly dynamic, supporting O(log N) insertions and deletions. It is built upon a standard balanced binary search tree, such as a Red-Black tree A Dichromatic Framework for Balanced Trees^[2] or an AVL tree.

In this variant, each node stores a single interval. The tree is ordered by the low endpoint of the intervals. To handle overlaps efficiently, each node is augmented with an additional value called max_high, which stores the maximum high endpoint of any interval in the subtree rooted at that node, including the node itself.

When a new interval is inserted or deleted, the underlying balanced tree performs its standard rotations to maintain its height constraints. During these rotations, the max_high values must be updated bottom-up to ensure the augmentation remains accurate. When a Red-Black tree performs a left rotation on a node X and its right child Y, Y becomes the new parent of X. The left child of Y becomes the new right child of X. The max_high values must be updated to reflect this new geometry. First, X (now a child) updates its max_high by taking the maximum of its own interval's high, its left child's max_high, and its new right child's max_high. Then, Y (the new parent) updates its max_high by taking the maximum of its own interval's high, its new left child's (X) max_high, and its right child's max_high. This constant-time mathematical operation ensures the tree remains perfectly synchronized without requiring a full recalculation of the subtree. When an interval is inserted at a leaf, the algorithm walks up the tree to the root, updating max_high at each ancestor in O(log N) time.

To find all intervals overlapping a query interval [q_low, q_high], the search begins at the root and follows a recursive traversal:

def search_overlaps(node, query):
    overlaps = []
    if node is None:
        return overlaps
    
    # Check if the current node's interval overlaps the query
    if node.low <= query.high and node.high >= query.low:
        overlaps.append(node.interval)
    
    # If the left child exists and its max_high is >= query.low,
    # there might be overlapping intervals in the left subtree.
    if node.left is not None and node.left.max_high >= query.low:
        overlaps.extend(search_overlaps(node.left, query))
    
    # Since the tree is sorted by 'low', we only search the right
    # subtree if the query's high is >= the current node's low.
    if node.right is not None and query.high >= node.low:
        overlaps.extend(search_overlaps(node.right, query))
        
    return overlaps

The max_high augmentation allows the algorithm to prune subtrees that cannot possibly contain an overlapping interval. If the left child's max_high is strictly less than the query's low, no interval in the left subtree extends far enough to the right to overlap the query, and the entire left subtree is skipped. Since the tree is sorted by low, the algorithm only searches the right subtree if the query's high is greater than or equal to the current node's low. This pruning mechanism guarantees the O(k log N) query time.

Discovery and History

The interval tree was discovered independently in 1980 by two researchers working in different contexts. Prior to 1980, the standard approach for managing intervals was the segment tree, introduced by Jon Bentley in 1977 Algorithms for Klee's rectangle problems^[3]. While the segment tree provided O(log N + k) query time, it required intervals to be split across multiple nodes, resulting in O(N log N) space complexity Segment tree^[4].^[29] The quest for an O(N) space structure was a recognized open problem in computational geometry.

Herbert Edelsbrunner, then at the Technical University of Graz in Austria, formalized the centered interval tree in his 1980 report Dynamic Rectangle Intersection Searching^[5]. Edelsbrunner was investigating the need to report intersections among orthogonal rectangles in multidimensional space. He demonstrated that a one-dimensional interval tree could be generalized to higher dimensions to solve the rectangle intersection problem in optimal time. He later expanded on this in his 1983 publication A new approach to rectangle intersections, Part I^[6].

Concurrently, Edward M. McCreight at the Xerox Palo Alto Research Center developed a highly similar structure. McCreight's 1980 technical report, Efficient algorithms for enumerating intersecting intervals and rectangles^[7], was motivated by the physical design of Very Large Scale Integration circuits. Routing solid wires on a silicon chip required fast algorithms to detect overlapping physical regions to prevent electrical shorts. McCreight later expanded on this work in his 1985 paper Priority Search Trees^[8], which introduced a related but distinct data structure, though his 1980 work laid the foundation for dynamic interval management.

The augmented interval tree variant gained widespread recognition after being featured in the textbook Introduction to Algorithms^[9] by Cormen, Leiserson, Rivest, and Stein. The textbook formalized the methodology of augmenting a Red-Black tree with the max_high field, standardizing the dynamic interval tree for generations of computer science students.

In the late 1990s and early 2000s, researchers adapted the interval tree for databases. Lars Arge and Jeffrey Scott Vitter introduced the External Memory Interval Tree in 2003 Optimal External Memory Interval Management^[10], modifying the structure to minimize disk input and output operations. Around the same time, Hans-Peter Kriegel, Marco Pötke, and Thomas Seidl published the Relational Interval Tree in 2000 Managing Intervals Efficiently in Object-Relational Databases^[11], which mapped the centered interval tree logic onto standard SQL tables and B+ tree indexes.

Important Variants

Several variants of the interval tree have been developed to address specific computing constraints, particularly regarding disk storage, memory layout, and specialized data distributions.

External Memory Interval Tree

Standard pointer-based interval trees perform poorly when stored on hard drives due to random memory access patterns. The external memory interval tree groups intervals into disk blocks. It uses a weight-balanced B-tree as a backbone The ubiquitous B-tree^[12]. Each node in the backbone manages a set of intervals, distributing them into secondary structures that fit within a single disk page. This guarantees that stabbing queries require O(log_B N + k/B) disk accesses, where B is the block size. This variant is critical for spatial databases where the interval dataset exceeds the available random-access memory.

Relational Interval Tree

The Relational Interval Tree is a virtual index structure designed for relational databases. Instead of building a custom tree in memory, it assigns a unique integer to every node in a conceptual binary tree spanning the data domain. Each interval is assigned to the highest node, called the fork node, that falls within its bounds. Because the conceptual tree is perfectly balanced and mapped to integers, the fork node can be computed in O(1) time using bitwise operations, specifically by finding the most significant bit where the binary representations of the lower and upper bounds differ. The database then stores the intervals in standard B+ trees keyed by these node integers. SQL queries compute the required fork nodes on the fly and retrieve overlapping intervals using standard relational joins.

Implicit Interval Tree

An implicit interval tree stores the tree in a contiguous array, eliminating the memory overhead of left and right child pointers. The root is placed at index 0. The left child of a node at index i is located at index 2i + 1, and the right child is at index 2i + 2. The max_high values are stored in a parallel array or interleaved in a structure. Because there are no pointers, the CPU can prefetch adjacent array elements, drastically reducing cache misses during a traversal. This variant is highly effective for static datasets where the tree is built once and queried millions of times.

Nested Containment List

While not strictly a tree, the Nested Containment List is a closely related structure optimized for intervals with high containment rates, such as genomic data ^[13]. It organizes intervals by containment rather than arbitrary overlap. If one interval is entirely contained within another, it is stored as a child of the larger interval. This provides faster query times in specific biological datasets while maintaining O(N) space, serving as a highly specialized alternative to the standard interval tree.

Real-World Applications

Interval trees are heavily utilized in systems that manage spatial, temporal, or genomic data, acting as the invisible engine behind many modern computing operations.

Bioinformatics and Genomics

Genomic analysis relies on overlapping annotations, such as finding which genetic variants intersect with known coding genes. The human genome consists of over three billion base pairs, and annotations are represented as intervals containing a chromosome identifier, a start position, and an end position. These are often stored in standardized formats like Browser Extensible Data files. Tools like BEDTools, developed by Aaron Quinlan and Ira Hall in 2010 BEDTools: a flexible suite of utilities for comparing genomic features^[14], use interval trees to perform genome arithmetic. When a researcher intersects a file of millions of sequencing reads with a file of known genes, BEDTools builds an interval tree of the genes in memory. It then streams the sequencing reads one by one, querying the interval tree to find overlaps. This avoids the O(N^2) complexity of comparing every read to every gene, reducing a computation that would take days into one that takes seconds.

The UCSC Genome Browser^[15] employs interval trees to quickly retrieve and render tracks of genomic features that fall within the user's viewing window. Modern implementations often use implicit interval trees or augmented lists AIList: fast intersect operations for biological intervals^[16] to maximize cache efficiency, as the sheer volume of genomic data requires extreme optimization.

Operating Systems and Memory Management

Operating systems must track the virtual memory areas allocated to processes. Each virtual memory area is an interval of memory addresses. When a program accesses a memory address, the kernel must quickly determine which area contains that address to handle page faults, execute memory-mapped file operations, or enforce security permissions. The Linux kernel historically relied on augmented Red-Black interval trees to manage these areas Linux kernel source tree^[17]. Every time a process called mmap to allocate memory, the kernel inserted a new interval into the tree. Although recent kernel versions have transitioned to the Maple tree^[18] for better concurrency and lockless read operations, the interval tree was the standard mechanism for Linux memory management for over a decade.

Temporal Databases

Temporal databases track data that is valid for specific periods. A standard relational database only stores the current state of the world. A temporal database stores the history of states.^[30] A record might have a valid-from and valid-to timestamp, representing the period during which a fact was true in the real world (valid time) or the period during which it was stored in the database (transaction time).^[31] Querying the database for all records active on a specific date, such as finding all employees who were active on January 1, 2020, is a stabbing query. Systems like IBM Db2 temporal tables^[19], PostgreSQL range types^[20], and Oracle Temporal^[21] use interval tree logic or equivalent spatial indexes to execute these queries efficiently. The SQL:2011 standard formalized temporal features, driving the need for optimized interval indexing in enterprise database engines. The Timeline Index, developed for the SAP HANA in-memory database, uses interval tree concepts to process temporal queries over enterprise data ^[22].

Computer Graphics and Document Object Models

In rendering engines and windowing systems, objects are bounded by two-dimensional or three-dimensional boxes. To determine which objects intersect the camera's view frustum or which windows overlap on a screen, the system uses a sweep-line algorithm. An imaginary line sweeps across the screen from left to right. When the line hits the left edge of a bounding box, the box's vertical interval (its top and bottom coordinates) is inserted into an active interval tree. When the line hits the right edge of the box, the interval is deleted. At any point, the system can query the interval tree to find all objects that overlap a specific vertical coordinate. This reduces the number of expensive pixel-level collision checks from O(N^2) to O(N log N), enabling real-time rendering in video games and graphical user interfaces. Interval trees have also been used to manage the Document Object Model in web browsers, allowing rendering engines to efficiently find and update overlapping HTML tags without redrawing the entire page A Web Browser and Editor^[23].

Significance and Tradeoffs

The interval tree is a foundational data structure in computer science Data Structures and Algorithms in Java^[24] because it provides an optimal balance of O(N) space and O(log N + k) query time for one-dimensional ranges. By augmenting a standard balanced tree, developers can add interval querying capabilities to existing software libraries with minimal overhead.

Comparison to Related Structures

The interval tree is often compared to the segment tree, the priority search tree, and the range tree. A segment tree splits intervals into smaller elementary segments, storing each segment in multiple nodes.^[29] This allows it to answer queries about the union or length of overlapping intervals easily, but it consumes O(N log N) space. The interval tree keeps intervals intact, strictly requiring O(N) space.

The priority search tree is a hybrid of a binary search tree and a priority queue. It is optimized for half-infinite range queries and is less commonly used for pure interval overlap problems. Range trees are designed for multi-dimensional point data rather than continuous intervals, making them unsuitable for duration or overlap tracking without significant modification.

Limitations in Higher Dimensions

The interval tree has specific limitations. It does not generalize efficiently to multiple dimensions Computational Geometry: Algorithms and Applications^[25]. While a two-dimensional interval tree can be constructed by nesting trees, the query time degrades to O(log^2 N + k), and the implementation becomes highly complex. For multidimensional spatial data, such as geographic maps or 3D environments, R-trees R-trees: A Dynamic Index Structure for Spatial Searching^[26], kd-trees, or Bounding Volume Hierarchies are generally preferred.

Cache Locality

Additionally, the pointer-based nature of the augmented interval tree can lead to poor cache locality on modern processors. Traversing nodes scattered across the heap causes cache misses. For static datasets that are queried millions of times, a flat array of sorted endpoints or an implicit interval tree often outperforms the standard pointer-based interval tree in practice, despite having the same asymptotic complexity Filtering Search: A New Approach to Query-Answering^[27]. The overhead of maintaining the max_high values also makes the interval tree slightly slower for pure point-insertions compared to a standard Red-Black tree.

Despite these tradeoffs, the interval tree remains the standard algorithmic solution for one-dimensional overlap problems, bridging the gap between theoretical computational geometry and practical software engineering.