Моделирование и оптимизация декартова дерева

Написать полностью программу и текст.

Моделирование и оптимизация декартова дерева

Реализовать класс «Декартово Дерево»

Реализовать необходимые для класса функции: конструкторы, деструкторы, нужные методы (вставка, поиск по ключу, удаление элемента, построение дерева из списка значений, объединение деревьев, пересечение деревьев) Реализовать поиск значения допустимой для дерева функции на отрезке Реализовать групповое изменение значений в определенном отрезке Решить задачи в двух вариантах: 1) быстром (в результате операций на деревьях получаем новое дерево, старыми не пользуемся), 2) безопасном (результатом операции на деревьях становится новое дерево, операнды не меняются и готовы к дальнейшему применению) Для выполнения групповых операций реализовать отложенное выполнение команд Оптимизировать построенный код: 1) по производительности, 2) по потреблению памяти

Продемонстрировать работу декартова дерева на произвольных отрезках и при различных групповых функциях (представить пример поиска k-ой порядковой статистики) Проиллюстрировать оценки структуры данных по памяти и производительности