Interval tree

Deep dive

How it works

In: a query range [qs, qe) (a point is a one-unit range) · Out: every stored interval that overlaps it · State: intervals sorted by start plus a parallel max_end array (built once) · Cost: build O(n log n); query O(log n + k) for k results Three families, all answering overlap(q) = { i : i.start < q.end && q.start < i.end }.

1. Augmented balanced BST (CLRS ch. 14): key = start; each node stores max_end of its subtree. Query at node n: if n.max_end <= q.start skip the subtree; else visit left; if n.start < q.end, report n if n.end > q.start and visit right. Insert/delete as in the base tree, recomputing max_end up the path and on rotations.
2. Centered interval tree (Edelsbrunner): pick a centre c; intervals containing c stay at the node, kept twice (sorted by start, sorted by end); the rest go left or right. A query left of c scans the by-start list until start >= q.end, then recurses left. Build O(n log n), query O(log n + k), O(n) space, but rebuilding is needed on change.
3. Sorted/implicit array: sort by start once; the "tree" is just index arithmetic over the array (node = midpoint of an index range, or level layout as in cgranges), with max_end in a parallel array. No pointers, no per-node allocation.

sorted by start:   [0..........mid..........n)      node(mid), max_end[mid] = max end over [lo,hi)
                    left range   right range         prune left if max_end[left mid] <= q.start
                                                     skip right if iv[mid].start >= q.end

Nested containment list (Alekseyenko and Lee): sort by (start, -end), move intervals contained in another into a sublist of it. Each list then has increasing starts and ends, so a query is one binary search per nesting level. Depth = nesting depth, so it is excellent for typical annotations and weak for heavily nested sets.

Code

/// Static interval tree: intervals sorted by start; the balanced BST is implicit
/// (node = midpoint of an index range), `max_end[i]` = max end in i's subtree.
/// Half-open intervals [start, end).
pub struct IntervalTree<T> {
    iv: Vec<(u32, u32, T)>, // sorted by start
    max_end: Vec<u32>,      // parallel array, same index
}

impl<T> IntervalTree<T> {
    pub fn build(mut iv: Vec<(u32, u32, T)>) -> Self {
        iv.sort_by_key(|x| x.0);
        let mut max_end = vec![0; iv.len()];
        Self::fill(&iv, &mut max_end, 0, iv.len());
        IntervalTree { iv, max_end }
    }

    fn fill(iv: &[(u32, u32, T)], m: &mut [u32], lo: usize, hi: usize) -> u32 {
        if lo >= hi { return 0; }
        let mid = lo + (hi - lo) / 2;
        let best = iv[mid].1
            .max(Self::fill(iv, m, lo, mid))
            .max(Self::fill(iv, m, mid + 1, hi));
        m[mid] = best;
        best
    }

    /// Calls `f` for every interval overlapping [qs, qe). Stabbing query: qe = qs + 1.
    pub fn overlaps(&self, qs: u32, qe: u32, mut f: impl FnMut(&(u32, u32, T))) {
        self.walk(0, self.iv.len(), qs, qe, &mut f);
    }

    fn walk(&self, lo: usize, hi: usize, qs: u32, qe: u32, f: &mut impl FnMut(&(u32, u32, T))) {
        if lo >= hi { return; }
        let mid = lo + (hi - lo) / 2;
        if self.max_end[mid] <= qs { return; }       // nothing in this subtree ends after qs
        self.walk(lo, mid, qs, qe, f);
        let x = &self.iv[mid];
        if x.0 >= qe { return; }                     // this and all right starts are >= qe
        if x.1 > qs { f(x); }
        self.walk(mid + 1, hi, qs, qe, f);
    }
}

#[test]
fn matches_brute_force() {
    let mut seed = 12345u64;
    let mut rnd = |n: u32| { seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407); ((seed >> 33) as u32) % n };
    for round in 0..200 {
        let ivs: Vec<(u32, u32, usize)> = (0..round % 60)
            .map(|i| { let s = rnd(1000); (s, s + 1 + rnd(200), i) }).collect();
        let tree = IntervalTree::build(ivs.clone());
        for _ in 0..50 {
            let (qs, len) = (rnd(1100), 1 + rnd(100));
            let mut got = vec![];
            tree.overlaps(qs, qs + len, |x| got.push(x.2));
            got.sort();
            let want: Vec<usize> = ivs.iter().filter(|x| x.0 < qs + len && qs < x.1).map(|x| x.2).collect();
            assert_eq!(got, want);
        }
    }
}

The type is static: it is built once from a Vec. Booking check = overlaps with the requested slot; any hit is a conflict.

Complexity and constants

• Build: one sort, O(n log n); the max_end pass is O(n) and sequential.
• Query: O(log n + k) in the balanced case. One long interval does not break it (the max_end test is exact), but a result is only found after descending to it, so cost grows with k.
• Bytes: this code stores (start, end, payload) plus 4 bytes of max_end, i.e. 16 bytes per interval for a u32 payload. A pointer-based BST adds two child pointers and usually a heap allocation per node.
• Cache misses: the first few levels stay in cache; the lower levels of a binary traversal miss about once per level on large arrays.

Efficiency

• Cost: the cgranges README benchmark (GENCODE BED with about 1.2M lines indexed, then queried with a second BED; their hardware) reports 9.0 s and 19.1 MB for the implicit augmented tree against 201.9 s and 478.5 MB for bedtools-style binning for indexing that BED, and 17.4 s / 27.2 MB for a centered tree. Treat as order of magnitude for that workload, not a guarantee. The bound is memory latency (pointer or index chasing), not arithmetic.
• Levers:
  • implicit array instead of node pointers — fewer bytes and allocations; the README numbers above (cgranges README) — static data.
  • van Emde Boas in-order layout of the nodes — better locality across levels (COITrees README says it tends to win for large sets with many queries) — large static sets.
  • sorted queries with a "continue from the previous result" cursor — reuses the previous answer (COITrees SortedQuerent) — queries arrive sorted by position, as in BAM-order reads.
  • bulk build (sort once) instead of n inserts — one sequential sort, no rebalancing, no per-node allocation — whole set known up front.
  • SIMD on blocks of starts/ends — used by rust-lapper (NEON, AVX2) and COITrees — leaf scans.
• Naive → standard → state of the art:
  • linear scan of all intervals · O(n) per query
  • augmented balanced BST · O(log n + k) per query, pointer chasing
  • implicit sorted array, cache-oblivious layout, SIMD leaves · same big-O, fewer cache misses (COITrees, rust-lapper)

Implementation notes

• Use u32/i32 coordinates when they fit (human chromosome length is under 2^32 bases); halving key width doubles the intervals per cache line.
• Keep payloads out of the hot arrays when large: index (start, end, id) and fetch the payload only for hits.
• For queries over millions of reads, sort the queries and walk them in order; adjacent queries touch the same nodes.
• Reuse one result buffer or callback (as here) instead of returning a Vec per query: no allocation per call.
• Dynamic data with few updates: keep a big static tree plus a small unsorted buffer scanned linearly, and rebuild when the buffer passes a threshold (a technique, not a named library).
• Rostering with one worker: if the stored set is non-overlapping, check only the predecessor and successor start.

Pitfalls

• Closed vs half-open mixing: an interval ending at 9 and one starting at 9 either clash or not; pick one convention for the whole system.
• Zero-length intervals (start == end) never overlap anything under half-open rules; reject or widen them at ingestion.
• Pruning on max_end computed before inserting breaks queries: repair max_end on every insert, delete and rotation.
• Sorting by start only, then scanning back from the last start < q.end, is O(n) with a long early interval; the max_end augmentation is what prevents it.
• Nested containment lists get one binary search per nesting level, so deeply nested sets (whole-chromosome features over genes over exons) cost more levels.
• Time zones and DST: for bookings, convert to UTC instants before indexing; wall-clock intervals can be ambiguous or empty.

Variants and alternatives

In production

• Genomics: cgranges-style implicit trees and COITrees serve BED intersect/coverage tools, rust-bio ships interval trees for Rust bioinformatics code; bedtools uses binning instead (per the cgranges README).
• Operating systems: the Linux kernel documents its interval tree as an augmented red-black tree (kernel docs).
• Scheduling: booking and rostering back ends use the same overlap lookup over existing slots; check each product for its actual structure.

Implementations

Sources

• Thomas H. Cormen et al., Introduction to Algorithms, ch. 14.3 "Interval trees" (augmenting data structures).
• Herbert Edelsbrunner, Dynamic data structures for orthogonal intersection queries, Technical report, TU Graz, 1980 (centered interval tree).
• Alexei V. Alekseyenko, Christopher J. Lee, Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases, Bioinformatics 23(11):1386-1393, 2007. paper · code
• Heng Li (lh3), cgranges README (design and benchmark). code
• dcjones, COITrees README (van Emde Boas layout, SIMD, sorted querent). code
• Linux kernel documentation, Red-black Trees (rbtree) (interval tree as an augmented rb tree). docs