Kenneth Adam Miller wrote:

With regards to the ICL data structure, can anybody tell me what the space and time complexity is of the various interval_map types (split and regular)?

It's not as good as it could be, if it used an interval tree. You'll find discussion of this if you search for the library's review in the mailing list archive. Regards, Phil.