Range-Based DSA Applications

Combining BTreeMap and BTreeSet range queries (.range()), boundary queries (.first_key_value(), .last_key_value()), and mutations builds classic data-structure and algorithmic patterns that require balanced search trees.

1. Merging Overlapping Intervals with BTreeMap<Start, End>

A BTreeMap<i64, i64> mapping each disjoint interval's start to its end can insert a new interval [new_start, new_end] and coalesce all overlapping intervals in $O((1 + k) \log n)$ time:

use std::collections::BTreeMap;

struct IntervalSet {
    // Invariant: disjoint intervals `start -> end` where `start <= end`
    intervals: BTreeMap<i64, i64>,
}

impl IntervalSet {
    fn new() -> Self {
        Self {
            intervals: BTreeMap::new(),
        }
    }

    fn insert(&mut self, mut start: i64, mut end: i64) {
        // 1. Check if the interval immediately preceding or at `start` overlaps:
        if let Some((&prev_start, &prev_end)) = self.intervals.range(..=start).next_back() {
            if prev_end >= start {
                start = prev_start;
                end = end.max(prev_end);
            }
        }

        // 2. Collect all existing intervals starting in `start..=end` and merge them:
        let overlapping_starts: Vec<i64> = self
            .intervals
            .range(start..=end)
            .map(|(&s, &e)| {
                end = end.max(e);
                s
            })
            .collect();

        for s in overlapping_starts {
            self.intervals.remove(&s);
        }

        self.intervals.insert(start, end);
    }
}

fn main() {
    let mut set = IntervalSet::new();
    set.insert(1, 4);
    set.insert(8, 10);
    set.insert(3, 8); // Bridges [1, 4] and [8, 10] into [1, 10]!
    set.insert(15, 20);

    println!("Merged intervals: {:?}", set.intervals);
}

Merged intervals: {1: 10, 15: 20}

2. Sliding-Window Multiset (Minimum and Maximum in a Moving Window)

Because BTreeSet<T> only stores unique elements, a multiset (bag) that allows duplicate elements while supporting $O(\log n)$ .first_key_value() (minimum) and .last_key_value() (maximum) is modeled in Rust as BTreeMap<T, usize> (mapping each value to its occurrence count):

use std::collections::BTreeMap;
use std::collections::btree_map::Entry;

struct MultiSet<T> {
    counts: BTreeMap<T, usize>,
}

impl<T: Ord> MultiSet<T> {
    fn new() -> Self {
        Self {
            counts: BTreeMap::new(),
        }
    }

    fn insert(&mut self, value: T) {
        *self.counts.entry(value).or_insert(0) += 1;
    }

    fn remove_one(&mut self, value: T) {
        if let Entry::Occupied(mut occ) = self.counts.entry(value) {
            if *occ.get() > 1 {
                *occ.get_mut() -= 1;
            } else {
                occ.remove();
            }
        }
    }

    fn min(&self) -> Option<&T> {
        self.counts.first_key_value().map(|(k, _)| k)
    }

    fn max(&self) -> Option<&T> {
        self.counts.last_key_value().map(|(k, _)| k)
    }
}

fn main() {
    let nums = [4, 2, 2, 9, 1];
    let k = 3;
    let mut window = MultiSet::new();

    for (i, &x) in nums.iter().enumerate() {
        window.insert(x);
        if i >= k {
            window.remove_one(nums[i - k]);
        }
        if i + 1 >= k {
            println!(
                "Window {:?} -> min={}, max={}",
                &nums[i + 1 - k..=i],
                window.min().unwrap(),
                window.max().unwrap()
            );
        }
    }
}

Window [4, 2, 2] -> min=2, max=4
Window [2, 2, 9] -> min=2, max=9
Window [2, 9, 1] -> min=1, max=9

3. String Prefix Search Using .range()

To find all keys in a BTreeSet<String> or BTreeMap<String, V> that start with a given prefix, start a .range(prefix..) at prefix and .take_while(|k| k.starts_with(prefix))—which stops scanning as soon as the first key past the prefix is reached in $O(\log n + k)$ time.