Interval Tree

An interval tree is a tree data structure that holds intervals and supports stabbing queries — given a point x, find all intervals that contain x — in O(log n + k) time, where k is the number of reported intervals.

The canonical implementation is the augmented interval tree: a binary search tree keyed on interval start, where each node stores the maximum endpoint in its subtree. A stabbing query visits only those subtrees whose maximum endpoint is at least x.

The crate here exposes a builder that constructs the tree from a list of intervals and a query method that returns the indices (or any associated payload) of all matching intervals.

Rust Implementation

The Rust crate lives at interval_tree/src/lib.rs; build & run it with:

$ cd interval_tree && cargo run
$ cd interval_tree && cargo test

Generated API reference for the Interval Tree crate. View the rendered API reference →

  1//! Interval tree for overlap queries on half-open `[lo, hi)` intervals.
  2//!
  3//! An `Interval<T>` is a tagged pair `(lo, hi)` with an associated
  4//! payload. This crate builds the simple static interval tree described by
  5//! the CLRS-style construction:
  6//!
  7//! * median-split on `mid = (lo + hi) / 2`
  8//! * store intervals whose midpoint lies on the left of `mid` in `left`
  9//! * store intervals whose midpoint lies on the right of `mid` in `right`
 10//! * store intervals that contain `mid` in `middle` (their `lo <= mid <= hi`)
 11//!
 12//! [`IntervalTree::query`] returns every interval whose `[lo, hi)` overlaps
 13//! a query interval `[qlo, qhi)`.
 14//!
 15//! The implementation is the canonical `O(n log n)` build / `O(k log n)`
 16//! query variant; it is built once on construction and immutable
 17//! thereafter.
 18
 19/// A half-open interval `[lo, hi)` carrying a payload.
 20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
 21pub struct Interval<T> {
 22    /// Inclusive lower bound.
 23    pub lo: i64,
 24    /// Exclusive upper bound.
 25    pub hi: i64,
 26    /// Associated payload.
 27    pub value: T,
 28}
 29
 30impl<T> Interval<T> {
 31    /// Construct a new interval.
 32    pub fn new(lo: i64, hi: i64, value: T) -> Self {
 33        debug_assert!(lo <= hi, "interval must satisfy lo <= hi");
 34        Self { lo, hi, value }
 35    }
 36
 37    /// Return the midpoint `(lo + hi) / 2`.
 38    fn mid(&self) -> i64 {
 39        (self.lo + self.hi) / 2
 40    }
 41
 42    /// Does this interval overlap `[qlo, qhi)`?
 43    fn overlaps(&self, qlo: i64, qhi: i64) -> bool {
 44        self.lo < qhi && qlo < self.hi
 45    }
 46
 47    fn contains_point(&self, p: i64) -> bool {
 48        self.lo <= p && p <= self.hi
 49    }
 50}
 51
 52/// Static interval tree.
 53#[derive(Debug)]
 54pub struct IntervalTree<T> {
 55    root: Option<Node<T>>,
 56}
 57
 58/// Internal node.
 59#[derive(Debug)]
 60struct Node<T> {
 61    mid: i64,
 62    middle: Vec<Interval<T>>,
 63    left: Option<Box<Node<T>>>,
 64    right: Option<Box<Node<T>>>,
 65}
 66
 67impl<T: Clone> IntervalTree<T> {
 68    /// Build an interval tree from a slice of intervals.
 69    ///
 70    /// # Panics
 71    ///
 72    /// Panics if any interval has `lo > hi`.
 73    pub fn new(intervals: &[Interval<T>]) -> Self {
 74        Self { root: build(intervals, 0, intervals.len()) }
 75    }
 76
 77    /// Return all intervals whose `[lo, hi)` overlaps `[qlo, qhi)`.
 78    pub fn query(&self, qlo: i64, qhi: i64) -> Vec<Interval<T>> {
 79        let mut out = Vec::new();
 80        if let Some(root) = self.root.as_ref() {
 81            query_node(root, qlo, qhi, &mut out);
 82        }
 83        out
 84    }
 85}
 86
 87fn build<T: Clone>(intervals: &[Interval<T>], lo: usize, hi: usize) -> Option<Node<T>> {
 88    if lo >= hi {
 89        return None;
 90    }
 91    // Split point of the slice
 92    let mid_idx = (lo + hi) / 2;
 93    let mid_point = intervals[mid_idx].mid();
 94
 95    let mut middle = Vec::new();
 96    let mut left_intervals = Vec::new();
 97    let mut right_intervals = Vec::new();
 98    for it in &intervals[lo..hi] {
 99        if it.contains_point(mid_point) {
100            middle.push(it.clone());
101        } else if it.hi < mid_point {
102            left_intervals.push(it.clone());
103        } else if it.lo > mid_point {
104            right_intervals.push(it.clone());
105        } else {
106            // Shouldn't happen: interval ends on one side, starts on other, but doesn't contain mid.
107            // Fall back to the midpoint comparison.
108            if it.mid() < mid_point {
109                left_intervals.push(it.clone());
110            } else {
111                right_intervals.push(it.clone());
112            }
113        }
114    }
115
116    Some(Node {
117        mid: mid_point,
118        middle,
119        left: build(&left_intervals, 0, left_intervals.len()).map(Box::new),
120        right: build(&right_intervals, 0, right_intervals.len()).map(Box::new),
121    })
122}
123
124fn query_node<T: Clone>(node: &Node<T>, qlo: i64, qhi: i64, out: &mut Vec<Interval<T>>) {
125    // Check middle (intervals that contain the node's `mid`).
126    for it in &node.middle {
127        if it.overlaps(qlo, qhi) {
128            out.push(it.clone());
129        }
130    }
131    if qlo < node.mid {
132        if let Some(left) = node.left.as_deref() {
133            query_node(left, qlo, qhi, out);
134        }
135    }
136    if qhi > node.mid {
137        if let Some(right) = node.right.as_deref() {
138            query_node(right, qlo, qhi, out);
139        }
140    }
141}

Applications

  • Stabbing queries on event intervals

  • Overlap detection in scheduling problems

  • Window-based aggregations (e.g. “which bookings are active now?”)