ЛКШ-2023, параллель 5. Лекция 4: Декартово дерево.

Двоичное дерево поиска, как способ построения дерева. Проблема балансировки дерева поиска. Декартово дерево - дерево со случайной балансировкой. Построение и единственность декартова дерева. Операции split и merge. Реализация декартова дерева на C++. Добавление и удаление элементов при помощи split и merge. Групповые запросы (например, количество элементов, сумма элементов). Нахождение k-й порядковой статистики.