Дерево отрезков (21 февраля)

1. Статическая оптимальность, алгоритм за O(n²)
2. Дерево отрезков с операциями сверху.
3. Дерево отрезков разбивает любой запрос на не более 2logn отрезков, для которых предподсчитана структура данных.
4. Какая операция подходит для дерева отрезков: ассоциативная, аддитивная (min, max, sum, product матрица, gcd, композиция перестановок, количество отрезков белого цвета)
5. Дерево отрезков с модификацией в точке, модификацией на отрезке.
6. Задача "числа добавляются, удаляются, говорить количество чисел со значением от L до R".
7. Более сложные операции: количество чисел в прямоугольнике, k-я порядковая статистика на отрезке за O(log³n)
8. Динамическое дерево отрезков и Offline идея "сжатия координат". Чем динамическое дерево отрезков слабее Treap?
9. Персистентное дерево отрезков, k-я порядковая статистика на отрезке неменяющегося массива за O(logn).
10. k-я порядковая статистика на отрезке меняющегося массива за O(log²n).