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

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

Двоичное дерево поиска. Или отсортированный массив, если данные не надо часто добавлять и удалять.