disjoint_interval_tree

https://github.com/anlsys/ruby-disjoint-interval-tree

A set of pairwise disjoint half-open intervals [a..b[, backed by an augmented AVL tree written in C. Insertion, point lookup, intersection queries and range removal are all logarithmic. Each node caches the hull of the subtree it roots, so intersection queries prune whole subtrees in O(1).