Декартово дерево

1. (L,R) = Split(T, x)
2. T = Merge(L, R)
3. Add. Через Split-Merge и одним запросом сверху.
4. Del. Через Split-Merge и одним запросом сверху.
5. Find K-th.
6. Количество, сумма всех элементов со значениями из [L..R]
7. Построение за O(n)
8. Randomized Trees (y можно не хранить)

Декартово дерево по неявному ключу

1. Ключ = позиция элемента. Неявный, т.к. восстанавливается из size-ов.
2. Split и Merge для дерева по неявному ключу.
3. Вставка на i-ю позицию, удаление с i-й позиции
4. Поменять местами два подотрезка массива.
5. Reverse подотрезка массива.
6. Прибавление на отрезке, присваивание на отрезке.

Неменяющийся массив.

1. Сумма на отрезке с предподсчетом за O(n)
2. Минимум на отрезке с предподсчетом за O(n²)
3. Минимум на префиксе.

Дерево отрезков

1. Построение за O(n)
2. Поменять 1 элемет
3. Сумма, минимум на отрезке
4. Прибавление на отрезке, присваивание на отрезке.