Oma is an OCaml library. It offers an implementation of the order maintenance data structure described in this paper.
Here is its documentation.
oma