Деревья поиска (BST)

Пишем

1. Несбалансированное дерево поиска
2. Персистентное дерево поиска
3. Treap: split

Задачи на деревья поиска

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-я порядковая статистика на отрезке