Декартово дерево и оптимизации к нему.

1. Писать на указателях (не на массивах)
2. Хранить специальную вершину Null.
3. Операции Calculate и Down
4. На каждом уровне Split и Merge выполнять ровно по одной операции Calculate и Down.

Корневая оптимизация

1. Структура это список отрезков. Отрезок = [L,R)
2. Частичные суммы, флажки reverse для отрезков, флажки add и equal для отрезков.
3. Операция Split. Режет, если нужно, и возвращает позицию, до которой дошла.
4. Операция Balance. Вызывается каждый sqrt(N) операций. Создает список из одного отрезка [0,N) и пересчитывает частичные суммы.
5. Д.З. Как делать минимум на отрезке?
6. Вставка и удаление по явному и неявному ключу. Операции на отрезках сохраняются.

Практика

1. reverse