Понимаем обычное дерево отрезков

Пусть у нас есть задача: поступают запросы двух видов для исходного массива. Первый вид - это замена конкретного элемента на другой. Второй - вычисление суммы/минимума или другой операции на диапазоне. Требуется обработать эти запросы.

Дерево отрезков решает эту задачу и позволяет обновить элемент, и дать ответ по диапазону за логарифмическое время O(logN). Сама структура данных строится за линейное время O(N). Затраты по памяти - 4N. Почему это так рассмотрим в конце статьи.

Смотреть статью