- Дерево отрезков
-
Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива.
Содержание
Дерево отрезков в памяти
Пусть наш массив имеет элементов: . Выберем такое, что . Тогда для хранения дерева отрезков понадобится массив из элементов. В ячейке при будет храниться число , где — функция, которую мы хотим вычислять от отрезков массива. Наиболее часто в качестве берутся функции суммы, произведения, минимумы и максимумы.
Дерево отрезков с одиночной модификацией
Изменение элемента
Пусть мы изменили значение . Тогда нам нужно присвоить элементу значение . После чего нужно обновить значения , и.т.д. Таким образом, на добавление элемента уйдёт действий.
Подсчёт функции для отрезка
Для подсчёта функции от элементов используется следующая рекурсивная процедура от аргументов . Здесь — элемент массива , в котором находится значение функции для отрезка , а — отрезок, на котором мы хотим посчитать функцию.
Если и , то ответ равен .
Если , то ответ равен .
Если , то ответ равен .
Иначе отрезок можно разбить на два отрезка: и . Тогда ответом будет .
Таким образом, вычисление функции на отрезке сводится к вычислению функции от элементов массива , соответствующих некоторым отрезкам . Можно показать, что при вычислении функции будет произведено рекурсивных вызовов.
Дерево отрезков с модификацией на интервале
Предположим, что мы хотим изменить значение не одной ячейки массива , а целого интервала (например, увеличить значения всех ячеек из интервала на заданное число ). Тогда хранения только массива недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.
Дерево отрезков для суммы (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
См. также
Дерево (структура данных) Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура Двоичные деревья Двоичное дерево · T-дерево Самобалансирующиеся двоичные деревья АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи B-деревья B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево Префиксные деревья Суффиксное дерево · Radix tree · Ternary search tree Двоичное разбиение пространства k-мерное дерево · VP-дерево Недвоичные деревья Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево Разбиение пространства R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков Другие деревья Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree Алгоритмы Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева Категории:- Алгоритмы
- Деревья (структуры данных)
Wikimedia Foundation. 2010.