Дерево поиска с заранее определенными свойством, является ли вершина листом
Нужна структура данных, поддерживающая 3 операции:
- Добавить лист
- Удалить лист
- Найти листья, имеющие в своем диапазоне значение запроса
В листе должна хранится информация об отрезке чисел (начало и конец).
Вероятно, это будет что-то похожее на бинарное дерево поиска, но есть ограничение: добавленные вершины обязаны быть листьями. При этом, добавлять вспомогательные вершины можно, в них будет хранится минимальные отрезок, в который полностью попадают оба потомка