Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива.

Дерево отрезков в памяти

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

Дерево отрезков с одиночной модификацией

Изменение элемента

Пусть мы изменили значение . Тогда нам нужно присвоить элементу значение . После чего нужно обновить значения , и.т.д. Таким образом, на добавление элемента уйдёт действий.

Подсчёт функции для отрезка

Для подсчёта функции от элементов используется следующая рекурсивная процедура от аргументов . Здесь — элемент массива , в котором находится значение функции для отрезка , а — отрезок, на котором мы хотим посчитать функцию.

Если и , то ответ равен .

Если , то ответ равен .

Если , то ответ равен .

Иначе отрезок можно разбить на два отрезка: и . Тогда ответом будет .

Таким образом, вычисление функции на отрезке сводится к вычислению функции от элементов массива , соответствующих некоторым отрезкам . Можно показать, что при вычислении функции будет произведено рекурсивных вызовов.

Дерево отрезков с модификацией на интервале

Предположим, что мы хотим изменить значение не одной ячейки массива , а целого интервала (например, увеличить значения всех ячеек из интервала на заданное число ). Тогда хранения только массива недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.

Дерево отрезков для суммы (RSQ)

Будем хранить массивы и с той же адресацией, что и массив (см. выше). Операция изменения будет состоять в увеличении значения всех ячеек от до на число . может быть как положительным, так и отрицательным.

имеет аргументы . Здесь — номер ячейки в массивах и , в которой хранится информация об отрезке , а — отрезок, на котором производится изменение.

В первую очередь при рекурсивном вызове увеличиваем на .

Далее, если и , то увеличиваем на .

Если , то вызываем рекурсивно .

Если , то вызываем .

Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .

Процедура вычисления суммы на отрезке модифицируется аналогично.

Если и , то значение суммы равно .

Если , то значение равно .

Если , то значение равно .

Иначе возвращаем .

Общая сложность операций modify и count составляет .

Дерево отрезков для максимума (RMQ)

Аналогично предыдущему случаю будем хранить массивы и . Операция будет иметь тот же смысл и те же аргументы.

Если и , то увеличиваем значения и на .

Если , то вызываем рекурсивно .

Если , то вызываем .

Иначе разбиваем отрезок на два: и . Производим 2 рекурсивных вызова и .

После рекурсивных вызовов (одного или двух), если они имели место, полагаем .

Осталось привести процедуру count вычисления максимума на отрезке.

Если и , то значение максимума равно .

Если , то значение равно .

Если , то значение равно .

Иначе значение максимума равно .

Общая сложность операций modify и count, как и в случае суммы, составляет .

Решение RMQ с помощью Sparse Table

Также задачу RMQ можно решать с помощью Sparse table. Эта структура данных позволяет находить максимум/минимум на отрезке за O(1) с препроцессингом за время O(n log n).

Препроцессинг:

Обозначим — максимум/минимум на отрезке от до . Массив можно заполнить динамически следующим образом:

1) ;

2) или соответственно.

Вычисление:

Ответ на отрезке равен (соответственно ), где lg — максимальная степень двойки, не превосходящая .

Пример:

Рассматриваем диапазон от 1 до 5. Максимальная степень двойки, которая помещается на него, это два, но она не покрывает весь диапазон, а только часть от 1 до 4. Максимум на этом отрезке можно получить, сравнив значения f[1,2] и f[2,2] (максимумы на отрезках от 1 до 4 и от 2 до 5).

Ссылки

• Дерево отрезков, его реализация на C++ и задачи, им решаемые, на сайте e-maxx.ru
• Реализация Дерева отрезков на Java

См. также

• Дерево Фенвика