Здравствуйте, SergASh, Вы писали:


SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.

Если требуется, то в CodeJam залита пробная версия augmented interval tree. Пока альфа, руки дойдут — добью.

Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли

NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.