Module Segmenttree
This module is a very simple implementation of "segment trees".
A segment tree of type 'a t
represents a mapping from a union of disjoint segments to some values of type 'a.
val make : ((int * int) * 'a) list -> 'a t
make [(i1, j1), v1; (i2, j2), v2; ...]
creates a mapping that associates to every integerx
the valuev1
ifi1 <= x <= j1
,v2
ifi2 <= x <= j2
, and so one. Precondition: the segments must be sorted.
val lookup : int -> 'a t -> 'a
lookup k t
looks for an image for keyk
in the interval treet
. RaiseNot_found
if it fails.