木を使うアルゴリズムなんてほとんど知らないんだが…
いちおうこんなのを考えてみた。
data Bound a = Inclusive a | Exclusive a | Unbounded -- 範囲の境界
type Range a = (Bound a, Bound a) -- (下限、上限)
data RangeMap k a =... -- kの範囲にaの値を対応させる写像。木で表現される。平衡木だとなおよい。
empty :: (Ord k) => RangeMap k a -- 空の写像
insert :: (Ord k) => Range k -> RangeMap k a -> RangeMap k a --既存の写像を部分的に上書き
update :: (Ord k) => Range k -> (a -> Maybe a) -> RangeMap k a -> RangeMap k a --既存の写像を部分的に更新
lookup :: (Ord k) => k -> RangeMap k a -> Maybe a

>そんでBoost氏がC++で書いてくれるのか？
いつのまにかBoost氏にされている訳だが。
「書きながらの抽象化」を示してくれるというなら頑張って書きますぜ。