Привет!

нужно сделать структуру, которая хранила бы следующие диапазоны значений
"занято от... и до..."
соответственно запросы должны быть типа
AddRange(int begin, int end); — добавить
HaveRange(int begin, int end); — есть ли этот диапазон целиком в добавленных, и если нет, то вернуть список диапазонов которых нет в добавленных.

Вот думаю, какую бы для этого структуру модифицировать, для более оптимальной работы.

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

FX>Вот думаю, какую бы для этого структуру модифицировать, для более оптимальной работы.

Отсортированное множество пар (итерируемое от меньшего к большему). Реализуется обычно через красно-черное дерево.
Легко искать перекрытия при вставке и при поиске диапазона. Легко проводить склейку и удаление диапазонов.

А в интернете есть где-нибудь код B-дерева для хранения ключей в виде регионов (от...до)?
что-то я никак не могу найти

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

FX>А в интернете есть где-нибудь код B-дерева для хранения ключей в виде регионов (от...до)?
FX>что-то я никак не могу найти

Зачем B-tree? Бинарное дерево будет эффективнее. Не надо будет бегать по спискам в ноде.

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

FX>Привет!

FX>нужно сделать структуру, которая хранила бы следующие диапазоны значений
FX>"занято от... и до..."
FX>соответственно запросы должны быть типа
FX>AddRange(int begin, int end); — добавить
FX>HaveRange(int begin, int end); — есть ли этот диапазон целиком в добавленных, и если нет, то вернуть список диапазонов которых нет в добавленных.

FX>Вот думаю, какую бы для этого структуру модифицировать, для более оптимальной работы.

http://en.wikipedia.org/wiki/Interval_tree
http://en.wikipedia.org/wiki/Segment_tree

Есть готовое, например http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/SearchStructures_ref/Class_Segment_tree_k.html