Внезапно, за пару часов нарисовалась пробная версия augmented interval tree. Ещё более внезапно она работает (вроде бы покрыл тестами все варианты) и работает быстро (в среднем быстрее раза в полтора-два чем конкуренты отсюда). Ну и самое внезапно — текущая реализация CompositeRange<T> не так уж и плоха, на списках до сотни элементов можно использовать её и не мучаться. Я не специально

Идея нагло слизана у wiki, https://code.google.com/archive/p/intervaltree/ использовался как референсная реализация, чтоб не изобретать велосипед.

P.S. Я пока не уверен, что нам нужен именно interval tree. С галёрки про NC-Lists подсказывают. Если есть другие интересные структуры для работы с интервалами — подкидываем.