An interval tree is a data structure designed to store a collection of intervals and quickly answer the question: which stored intervals overlap with a given point or range? If you have thousands or millions of intervals and need to find overlaps fast, a brute-force scan through all of them is painfully slow. An interval tree organizes those intervals in a tree structure so that overlap queries can be answered in time proportional to the logarithm of the number of intervals plus the number of results, rather than proportional to the total collection size. This makes it a go-to solution in fields where interval data is everywhere, from genomic coordinate lookups to scheduling engines to temporal databases.
The Problem That Makes Interval Trees Necessary
An interval is just a pair of values marking a start and an end: a gene that spans positions 1,000 to 5,000 on a chromosome, a hotel reservation from March 3 to March 7, or a sensor reading valid from timestamp 200 to timestamp 450. The fundamental query people need to run against a collection of these intervals is the overlap query (sometimes called an intersection query or a stabbing query). A stabbing query asks “which intervals contain this specific point?” while an intersection query asks “which intervals overlap with this other interval?” Both boil down to the same structural challenge.
If you only have a handful of intervals, you can just check each one. But real-world datasets often contain millions. A human genome annotation file can easily hold tens of millions of interval records. Checking every single one against your query is linear in the number of intervals, and doing that repeatedly across thousands of queries makes the total cost explode. Sorted arrays help somewhat if you only care about one endpoint, but intervals have two endpoints, and sorting by one does not guarantee useful ordering by the other. The interval tree was developed to handle exactly this mismatch.
How an Interval Tree Works
The classic interval tree, often attributed to computer scientist Edy Chung-Ping Zen and later popularized through textbooks, uses a divide-and-conquer strategy. Pick a center point (typically the median of all interval endpoints). Every interval in your collection either straddles that center point, lies entirely to its left, or lies entirely to its right. The straddling intervals get stored at the current node. The intervals lying entirely to the left go into a left subtree, and those lying entirely to the right go into a right subtree. Repeat recursively.
At each node, the straddling intervals are stored in a way that makes searching them efficient. A common approach keeps two sorted lists of those intervals: one sorted by their left endpoints, the other by their right endpoints. When a query arrives asking “which intervals contain point q?”, you compare q to the node’s center point. If q is to the left of center, you walk through the list sorted by left endpoints, picking up every interval whose left endpoint is at or before q, since you already know these intervals cross the center (which is to the right of q). If q is to the right, you do the mirror image using the list sorted by right endpoints. Then you recurse into the appropriate child subtree. The result is that each level of the tree processes only the intervals that are relevant, and you skip entire subtrees that cannot possibly contain overlapping intervals.
For a collection of n intervals, building the tree takes time proportional to n log n. A query that returns k results runs in time proportional to log n plus k. That “plus k” matters: the cost scales with how many answers there are, not how many intervals you stored. If only three intervals overlap your query out of ten million, you pay the logarithmic cost of navigating the tree plus a trivially small cost for those three results.
Queries Beyond Simple Stabbing
Stabbing queries (finding all intervals containing a single point) are the most discussed use case, but interval trees handle several related operations. An overlap query takes an interval as input rather than a single point and returns every stored interval that intersects it. The logic is similar: at each node, compare the query interval against the center point and walk through the sorted lists accordingly, but now you check whether the query interval overlaps the stored intervals rather than whether a point falls inside them.
Most implementations also support insertion and deletion without rebuilding the whole tree. You walk down the tree to find where a new interval belongs, add it, and possibly rebalance. Deletion works symmetrically. These dynamic operations keep the logarithmic guarantees as long as the tree stays balanced, which is typically maintained through standard balancing strategies borrowed from balanced binary search trees.
Some applications need an “envelope” query: what is the maximum (or minimum) value across all intervals covering a particular point? This is common in computational geometry and resource allocation, where you want to know the peak load at a given moment. Augmented interval trees can answer this by storing extra information at each node, such as the maximum endpoint in a subtree, allowing the query to prune branches that cannot contribute to the answer.
The Implicit Interval Tree
A standard interval tree uses pointers to connect parent and child nodes, which means each node carries overhead for those pointers. An implicit interval tree eliminates this overhead by laying out the tree in a flat array, where parent-child relationships are determined by index arithmetic rather than explicit pointers. If you have ever seen a binary heap stored in an array, where the children of position i live at positions 2i and 2i+1, the idea is the same.
This layout matters for performance in practice because modern processors are much faster at accessing memory sequentially than jumping around through pointers. A pointer-based tree causes cache misses every time you follow a link to a distant memory location, while an array-based tree keeps related data close together. The practical speedup can be substantial. A genomics toolkit called bedtk, built around an implicit interval tree, was shown to be several to tens of times faster than existing tools for genomic interval overlap queries while also using less memory.1PubMed Central. Bedtk: finding interval overlap with implicit interval tree That kind of real-world speedup from a relatively simple structural change illustrates how much the choice of tree layout can matter once your dataset is large enough.
The tradeoff is flexibility. Implicit interval trees work best when the set of intervals is known in advance and does not change frequently. Because the array layout depends on the total number of elements, inserting or deleting intervals requires shifting elements around or rebuilding portions of the array. For static or mostly-static datasets, that is perfectly fine. For highly dynamic workloads where intervals are constantly being added and removed, a pointer-based tree with rebalancing is usually a better fit.
External Interval Trees for Disk-Resident Data
When the interval collection is too large to fit in memory, the data lives on disk, and the cost model changes completely. In-memory operations are fast; reading a block of data from disk is orders of magnitude slower. The external interval tree adapts the interval tree concept for this reality by organizing data into disk-sized blocks and minimizing the number of disk reads needed per query.
An optimal external interval tree answers stabbing queries using a number of disk reads proportional to the logarithm of the data size (in terms of block size) plus the number of result blocks, and supports insertions and deletions with similarly efficient disk access costs.2SIAM Journal on Computing. Optimal External Memory Interval Management This makes the structure suitable for temporal databases and object-oriented databases where intervals represent valid-time ranges for records and the dataset far exceeds available RAM.
A related structure called the RI-tree was designed specifically for relational database engines. It maps interval queries onto standard B-tree indexes that database systems already provide, avoiding the need for custom storage engines. In experiments on an Oracle database server, the RI-tree outperformed competing dynamic interval access methods by a factor of up to 42 in disk accesses and nearly five times in query response time.3Academia.edu. Managing intervals efficiently in object-relational databases The underlying idea of translating interval endpoints into a single-dimensional key that a B-tree can handle efficiently has influenced how several commercial database systems implement temporal queries today.
Where Interval Trees Show Up in Practice
Genomics is probably the single largest consumer of interval tree implementations. A genome is essentially a coordinate system, and most genomic features (genes, exons, regulatory regions, variant calls) are intervals on that coordinate system. When a researcher asks “what genes overlap the region I just sequenced?” or “which known variants fall within this exon?”, they are issuing an interval overlap query. Tools that manipulate BED files, the standard format for genomic intervals, rely heavily on interval trees or closely related structures internally. The bedtk toolkit mentioned earlier supports sorting, merging, intersection, subtraction, and coverage calculation over genomic intervals, all powered by an implicit interval tree.4PubMed Central. Bedtk: finding interval overlap with implicit interval tree
Scheduling systems are another natural home. If you model resource reservations (conference rooms, machines, bandwidth slots) as time intervals, checking whether a new reservation conflicts with existing ones is an overlap query. Calendar applications, airline crew scheduling, and manufacturing job-shop scheduling all use interval-tree-like structures or algorithms descended from them. The query pattern is identical to the genomic case: you have a candidate interval and need to find everything it collides with.
Computational geometry uses interval trees as building blocks for more complex structures. Window queries in geographic information systems, collision detection in game engines, and range searching in spatial databases all involve detecting overlaps between regions, which in one dimension reduces to interval overlap and in higher dimensions extends through techniques discussed below. Even network routers have used interval-tree-inspired data structures for packet classification, where rules specify ranges of IP addresses and ports and incoming packets need to be matched against those ranges quickly.
Moving to Higher Dimensions
A one-dimensional interval tree handles intervals on a number line. But many real problems involve rectangles (two-dimensional intervals), boxes (three-dimensional), or higher-dimensional regions. The natural extension is to combine interval trees with other structures to handle each additional dimension.
For rectangle intersection in two dimensions, a common approach uses an interval tree on one axis and, at each node, a secondary structure (like another tree or sorted list) on the other axis. Early work on finding rectangle intersections in k-dimensional space identified three core problem variants: finding which rectangles in a stored set overlap a query rectangle, finding overlapping pairs as rectangles are inserted and deleted dynamically, and finding all overlapping pairs within a static set.5Journal of Algorithms. Finding intersection of rectangles by range search Each variant has a slightly different optimal solution, but all build on the same principle of decomposing the multi-dimensional problem into coordinated one-dimensional queries.
The cost grows with each additional dimension, and the constant factors in both time and space increase enough that alternatives like R-trees or k-d trees sometimes win in practice for very high dimensions. For two and three dimensions, though, interval-tree-based approaches remain competitive and are often preferred when the workload is heavily query-dominated rather than update-dominated.
Interval Trees Versus Similar Structures
If you search for “interval data structures,” you will run into segment trees, range trees, k-d trees, and R-trees. They all deal with ranges of values, but they solve slightly different problems and have different strengths.
A segment tree is the closest relative. It is built over a fixed set of endpoints and partitions the number line into elementary segments. Each interval is associated with the segments it covers. Segment trees are excellent when you need to answer aggregate queries over intervals (like “what is the sum of all values covering this point?”) and when the set of possible endpoints is known in advance. The main difference is that a segment tree is typically static: the set of possible intervals is bounded by the initial endpoint set. An interval tree, by contrast, handles arbitrary intervals without needing to know the endpoints ahead of time.
Range trees are designed for point data, not interval data. They answer questions like “which points fall within this box?” efficiently. If your data is naturally point-shaped (city locations, sensor readings at specific times), a range tree is the right tool. If your data has extent (start and end values), you want an interval tree. You can sometimes convert between the two representations, mapping each interval to a point in two dimensions (its start and end coordinates), but this conversion adds complexity and the resulting queries are less intuitive.
R-trees are the workhorse of spatial databases and geographic information systems. They group nearby objects into bounding rectangles and organize those rectangles hierarchically. R-trees handle arbitrary shapes in multiple dimensions and support both queries and updates gracefully. They sacrifice the tight worst-case guarantees of interval trees for flexibility and good average-case behavior on real-world spatial data. If your intervals are one-dimensional and your workload is query-heavy, an interval tree will generally outperform an R-tree. If your data is multi-dimensional and your workload mixes queries with frequent updates, an R-tree is often the more practical choice.
Common Misconceptions and Practical Pitfalls
One widespread confusion is between interval trees and segment trees. Many competitive programming resources and online tutorials use the terms loosely or even interchangeably, but they are different structures with different capabilities. If you are reading a tutorial that describes a “segment tree with lazy propagation,” that is not an interval tree. The naming collision has caused real implementation errors when developers pick up the wrong structure for their problem.
Another misconception is that interval trees are always the best choice for interval data. For very small collections (a few hundred intervals), the overhead of building and maintaining a tree is not worth it. A sorted list with binary search on one endpoint, followed by a linear scan of candidates, can be faster due to simpler code and better cache behavior. The crossover point depends on hardware and implementation details, but interval trees start to shine when the collection reaches thousands of intervals and the number of queries is large.
Balance maintenance is another practical issue that catches people off guard. A naive interval tree without any balancing scheme can degenerate into a linked list if intervals are inserted in a pathological order, causing query time to degrade to linear. Most textbook descriptions gloss over this by assuming balanced construction, but any production implementation needs to incorporate explicit balancing, either through red-black tree or AVL tree rotations, or by using the implicit array-based approach, which is inherently balanced.
Memory overhead is worth considering too. Each node in a pointer-based interval tree stores the interval, two pointers to children, and often auxiliary data like the maximum endpoint in the subtree. For very large datasets, this overhead adds up. The implicit interval tree approach addresses this, but as mentioned, it limits flexibility for dynamic updates. Choosing between pointer-based and array-based implementations is one of the first practical decisions when deploying an interval tree.
Concurrency and Modern Hardware
Traditional interval tree descriptions assume a single thread accessing the structure. On modern multi-core machines, this is often a bottleneck. If multiple threads are simultaneously querying and updating the tree, naive locking (putting a single lock around the whole tree) serializes all operations and defeats the purpose of having multiple cores.
Concurrent interval trees are an active area of research. The challenge is that an overlap query can touch many nodes spread across different parts of the tree, and an insertion or deletion can trigger rebalancing that affects nodes far from the insertion point. Fine-grained locking (one lock per node) reduces contention but adds complexity and per-node overhead. Lock-free approaches exist for simpler tree structures but are harder to adapt to interval trees because of the auxiliary data stored at each node.
In practice, many high-throughput systems sidestep the concurrency problem by partitioning the interval space. Each partition gets its own independent interval tree, and each thread or core handles a subset of partitions. This avoids contention entirely within a partition, at the cost of needing to merge results across partitions for queries that span the boundary. For genomic workloads, partitioning by chromosome is a natural and effective strategy, since intervals rarely cross chromosome boundaries.
Building One From Scratch Versus Using a Library
If you are a developer deciding whether to implement your own interval tree, the honest answer is that most standard library ecosystems do not include one out of the box. Languages like Python, Java, and C++ have balanced binary search trees and sorted containers in their standard libraries, but not interval trees specifically. This means you either pull in a third-party library or roll your own.
For Python, packages like intervaltree provide a straightforward API where you insert intervals and query for overlaps. For C++ and Java, several open-source libraries exist, though quality varies. If performance is critical and your dataset is static, an implicit interval tree stored in a flat array is relatively simple to implement yourself and delivers excellent cache performance. The core algorithm for building one is: sort all interval endpoints, lay them into an array representing a complete binary tree, and at query time walk down the tree using index arithmetic.
For genomics specifically, domain tools already embed interval trees internally. Bedtools, bedtk, and similar utilities handle BED-format files efficiently without requiring the user to think about the underlying data structure at all. If your problem is “I have genomic intervals and need overlaps,” reaching for one of these tools is almost always better than writing your own interval tree from scratch.
In database contexts, you rarely build an interval tree yourself either. Instead, you model the problem so that the database’s built-in indexing (B-tree or R-tree indexes) can handle the overlap queries. Some databases support range types natively: PostgreSQL, for example, has built-in range types with GiST index support that effectively implements interval-tree-like functionality within the database engine. Knowing that this capability exists can save you from building an external layer that duplicates what your database already provides.