День 3. Корневая.

1. С/C++: tree


2. Корневая
1. Корневая на массиве: сумма (два способа), минимум
2. Фаброзавтры: найти количество чисел равных x на отрезке
3. Корневая со split/rebuild: вставка, удаление, reverse на отрезке, количество ≤x на отрезке
4. Корневая со split/merge: то же, что и предыдущее, но быстрее
5. Отложенные операции (корневая по запросам): учим сортированный массив свежедобавленным элементам


3. k-я статистика на отрезке
1. За O(log³n) и O(log²n) бинпоиском по ответу
2. Задача на дерево отрезков: дан массив из нулей и единиц, найти k-ую единицу (решение за log²n с бинпоиском, и за logn спуском по дереву)
3. За O(logn) параллельным спуском по двум версиям


4. DCP в offline
1. Решение корневой за O(m^3/2)
2. Решение деревом отрезков по запросам без СНМ
3. Решение деревом отрезков по запросам с СНМ (удаления можно не делать)