838 Fundamental

Interval Tree — Stabbing Queries

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Interval Tree — Stabbing Queries" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Given a set of intervals [l, r] and a query point q, find all intervals that contain q (stabbing query). Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Given a set of intervals [l, r] and a query point q, find all intervals that contain q (stabbing query). Naive linear scan is O(n) per query. An interval tree answers stabbing queries in O(log n + k) where k is the number of reported intervals, after O(n log n) preprocessing. This enables efficient scheduling conflict detection (does event at time q overlap any existing booking?), genomic range queries (which genes cover position q?), and network packet classification (which firewall rules match this port range?). Interval trees are the data structure behind many calendar and scheduling applications.

🎯 Learning Outcomes

• Build an interval tree using a centered decomposition: for each node, store intervals crossing the center

• Organize crossing intervals in two sorted lists: by left endpoint and by right endpoint

• Implement stabbing query: follow left or right child based on q vs. center, query crossing intervals

• Understand the O(log n + k) query complexity and O(n log n) build complexity

• Compare with segment tree and augmented BST approaches to range queries

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Interval Tree for Stabbing Queries in OCaml *)

type interval = { lo: float; hi: float; id: int }

(* Each node: median, intervals spanning median (sorted by lo and hi),
   left subtree (all intervals < median), right subtree (all > median) *)
type tree =
  | Empty
  | Node of {
      median  : float;
      by_lo   : interval list;  (* sorted ascending by lo *)
      by_hi   : interval list;  (* sorted descending by hi *)
      left    : tree;
      right   : tree;
    }

let build (intervals : interval list) : tree =
  let rec build_rec ivs =
    match ivs with
    | [] -> Empty
    | _ ->
      (* Median of endpoints *)
      let endpoints = List.concat_map (fun iv -> [iv.lo; iv.hi]) ivs in
      let sorted_ep = List.sort compare endpoints in
      let n = List.length sorted_ep in
      let median = List.nth sorted_ep (n / 2) in
      (* Partition: spanning, left, right *)
      let spanning = List.filter (fun iv -> iv.lo <= median && iv.hi >= median) ivs in
      let left_ivs = List.filter (fun iv -> iv.hi < median) ivs in
      let right_ivs = List.filter (fun iv -> iv.lo > median) ivs in
      let by_lo = List.sort (fun a b -> compare a.lo b.lo) spanning in
      let by_hi = List.sort (fun a b -> compare b.hi a.hi) spanning in
      Node {
        median;
        by_lo; by_hi;
        left = build_rec left_ivs;
        right = build_rec right_ivs;
      }
  in
  build_rec intervals

(* Stab query: all intervals containing point x *)
let query (x : float) (tree : tree) : interval list =
  let rec query_rec t acc =
    match t with
    | Empty -> acc
    | Node { median; by_lo; by_hi; left; right } ->
      let acc = if x <= median then begin
        (* Scan by_lo until lo > x *)
        let rec scan = function
          | [] -> acc
          | iv :: rest -> if iv.lo > x then acc else iv :: scan rest
        in
        scan by_lo
      end else begin
        (* Scan by_hi (desc) until hi < x *)
        let rec scan = function
          | [] -> acc
          | iv :: rest -> if iv.hi < x then acc else iv :: scan rest
        in
        scan by_hi
      end in
      let acc = if x < median then query_rec left acc else query_rec right acc in
      acc
  in
  query_rec tree []

let () =
  let ivs = [
    {lo=1.0; hi=5.0; id=1};
    {lo=2.0; hi=8.0; id=2};
    {lo=6.0; hi=10.0; id=3};
    {lo=3.0; hi=7.0; id=4};
    {lo=9.0; hi=12.0; id=5};
  ] in
  let tree = build ivs in
  let queries = [0.0; 3.0; 6.5; 9.5; 15.0] in
  List.iter (fun x ->
    let results = query x tree in
    let ids = List.map (fun iv -> iv.id) results in
    Printf.printf "stab(%.1f): ids=[%s]\n" x
      (String.concat "," (List.map string_of_int (List.sort compare ids)))
  ) queries

Key Differences

Aspect	Rust	OCaml
Tree structure	`Option<Box<IntervalTree>>`	Algebraic type with `Leaf`
Sorted intervals	`Vec<(i64, i64)>`	`(int * int) list`
Null handling	`Option`	Pattern match on `Leaf`
Build complexity	O(n log n)	Same
Query complexity	O(log n + k)	Same
Memory	Compact Vec tuples	GC-managed list nodes

OCaml Approach

OCaml represents the interval tree with an algebraic type: type t = Leaf | Node of { center: int; left_sorted: interval list; right_sorted: interval list; left_child: t; right_child: t }. The stab q tree function pattern-matches on the tree structure. List.filter or binary search on sorted lists reports crossing intervals. OCaml's immutable default makes building the tree via let rec build natural. The List.sort and List.rev operations create the two sorted interval lists.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Interval Tree for Stabbing Queries in OCaml *)

type interval = { lo: float; hi: float; id: int }

(* Each node: median, intervals spanning median (sorted by lo and hi),
   left subtree (all intervals < median), right subtree (all > median) *)
type tree =
  | Empty
  | Node of {
      median  : float;
      by_lo   : interval list;  (* sorted ascending by lo *)
      by_hi   : interval list;  (* sorted descending by hi *)
      left    : tree;
      right   : tree;
    }

let build (intervals : interval list) : tree =
  let rec build_rec ivs =
    match ivs with
    | [] -> Empty
    | _ ->
      (* Median of endpoints *)
      let endpoints = List.concat_map (fun iv -> [iv.lo; iv.hi]) ivs in
      let sorted_ep = List.sort compare endpoints in
      let n = List.length sorted_ep in
      let median = List.nth sorted_ep (n / 2) in
      (* Partition: spanning, left, right *)
      let spanning = List.filter (fun iv -> iv.lo <= median && iv.hi >= median) ivs in
      let left_ivs = List.filter (fun iv -> iv.hi < median) ivs in
      let right_ivs = List.filter (fun iv -> iv.lo > median) ivs in
      let by_lo = List.sort (fun a b -> compare a.lo b.lo) spanning in
      let by_hi = List.sort (fun a b -> compare b.hi a.hi) spanning in
      Node {
        median;
        by_lo; by_hi;
        left = build_rec left_ivs;
        right = build_rec right_ivs;
      }
  in
  build_rec intervals

(* Stab query: all intervals containing point x *)
let query (x : float) (tree : tree) : interval list =
  let rec query_rec t acc =
    match t with
    | Empty -> acc
    | Node { median; by_lo; by_hi; left; right } ->
      let acc = if x <= median then begin
        (* Scan by_lo until lo > x *)
        let rec scan = function
          | [] -> acc
          | iv :: rest -> if iv.lo > x then acc else iv :: scan rest
        in
        scan by_lo
      end else begin
        (* Scan by_hi (desc) until hi < x *)
        let rec scan = function
          | [] -> acc
          | iv :: rest -> if iv.hi < x then acc else iv :: scan rest
        in
        scan by_hi
      end in
      let acc = if x < median then query_rec left acc else query_rec right acc in
      acc
  in
  query_rec tree []

let () =
  let ivs = [
    {lo=1.0; hi=5.0; id=1};
    {lo=2.0; hi=8.0; id=2};
    {lo=6.0; hi=10.0; id=3};
    {lo=3.0; hi=7.0; id=4};
    {lo=9.0; hi=12.0; id=5};
  ] in
  let tree = build ivs in
  let queries = [0.0; 3.0; 6.5; 9.5; 15.0] in
  List.iter (fun x ->
    let results = query x tree in
    let ids = List.map (fun iv -> iv.id) results in
    Printf.printf "stab(%.1f): ids=[%s]\n" x
      (String.concat "," (List.map string_of_int (List.sort compare ids)))
  ) queries

Deep Comparison

OCaml vs Rust: Interval Tree Stabbing

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement all_overlaps(l, r): find all intervals that overlap the query interval [l, r].

Add deletion support: mark intervals as deleted with a tombstone and rebuild when tombstone ratio exceeds 50%.

Compare interval tree vs. sorted array + binary search for stabbing queries at varying n.

Implement a segment tree-based approach for stabbing queries and compare with interval tree.

Handle open/closed interval endpoints: (l, r), [l, r), (l, r], [l, r] all handled correctly.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust