ЛКШ-2024, параллель 6. Лекция 2: Декартово дерево.

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

Видео ЛКШ-2024, параллель 6. Лекция 2: Декартово дерево. автора Denis Kirienko