BST (часть 1)

Четверг, 16 февраля 2017
Таймс, ауд. 405

Приложенные файлы

Описание

  • Пишем

    1. Декартово дерево
    2. Персистентное декартово дерево
  • Задачи на деревья поиска

    1. Сумма значений $l \le x \le r$
    2. Вставка, удаление, k-й элемент множества
    3. Добавить точку, удалить точку, вывести любую точку внутри области $d_i \le y \le u_i, x \le r_i$.
  • Задачи на персистентность

    1. 2D-запрос в онлайн за O(logn)
    2. (если останется время) k-я порядковая статистика на отрезке