BST (часть 1)

Пишем

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