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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Дерево отрезков в памяти[править | править вики-текст]

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

Дерево отрезков с одиночной модификацией[править | править вики-текст]

Изменение элемента[править | править вики-текст]

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

Подсчёт функции для отрезка[править | править вики-текст]

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

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

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

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

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

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

Дерево отрезков с модификацией на интервале[править | править вики-текст]

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

Дерево отрезков для суммы (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).

Решение за O(1) с препроцессингом и памятью O(N)[править | править вики-текст]

Для такого решения достаточно свести задачу RMQ к задаче LCA, построив декартово дерево из элементов вида , то есть - ключ, - приоритет. Приоритеты должны быть упорядочены снизу вверх, то есть в корне должен стоять элемент с наименьшим . Очевидно, такое дерево легко построить за , так как все ключи у нас упорядочены (это идущие друг за другом индексы элементов массива).

После этого ответом на любой запрос будет LCA двух вершин и . Индекс LCA будет лежать в , так как декартово дерево по ключу - двоичное дерево. Благодаря тому, что декартово дерево - пирамида по приоритету, эта же вершина будет иметь наименьший приоритет (значение элемента) из всех, находящихся в

Для задачи LCA известны несколько возможных решений за с препроцессингом и памятью . Такое решение является асимптотически оптимальным.

Ссылки[править | править вики-текст]

См. также[править | править вики-текст]