Деревья отрезков (3 декабря)

1. Дерево отрезков с операциями сверху
1. Построение за O(n), изменение в точке, запрос на отрезке
2. Модификация на отрезке
3. Динамическое дерево отрезков (координаты до 10⁹)
2. Идея сканирующей прямой. Обработка событий. На примере задачи: найти самую длинную цепочку точек, возрастающую по обеим координатам.
3. Дерево отрезков с операциями снизу
4. Дерево Фенвика для функции на префиксе