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

Дерево отрезков с операциями сверху

• Построение за O(n), изменение в точке, запрос на отрезке
• Модификация на отрезке
• Динамическое дерево отрезков (координаты до $10^9$)

Идея сканирующей прямой. Обработка событий. На примере задачи: найти самую длинную цепочку точек, возрастающую по обеим координатам.

Дерево отрезков с операциями снизу

Дерево Фенвика для функции на префиксе