- Дерево отрезков
-
Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов
массива.
Содержание
Дерево отрезков в памяти
Пусть наш массив
имеет
элементов:
. Выберем
такое, что
. Тогда для хранения дерева отрезков понадобится массив
из
элементов. В ячейке
при
будет храниться число
, где
— функция, которую мы хотим вычислять от отрезков массива. Наиболее часто в качестве
берутся функции суммы, произведения, минимумы и максимумы.
Дерево отрезков с одиночной модификацией
Изменение элемента
Пусть мы изменили значение
. Тогда нам нужно присвоить элементу
значение
. После чего нужно обновить значения
,
и.т.д. Таким образом, на добавление элемента уйдёт
действий.
Подсчёт функции для отрезка
Для подсчёта функции от элементов
используется следующая рекурсивная процедура
от аргументов
. Здесь
— элемент массива
, в котором находится значение функции для отрезка
, а
— отрезок, на котором мы хотим посчитать функцию.
Если
и
, то ответ равен
.
Если
, то ответ равен
.
Если
, то ответ равен
.
Иначе отрезок
можно разбить на два отрезка:
и
. Тогда ответом будет
.
Таким образом, вычисление функции на отрезке
сводится к вычислению функции от элементов массива
, соответствующих некоторым отрезкам
. Можно показать, что при вычислении функции будет произведено
рекурсивных вызовов.
Дерево отрезков с модификацией на интервале
Предположим, что мы хотим изменить значение не одной ячейки массива
, а целого интервала
(например, увеличить значения всех ячеек из интервала на заданное число
). Тогда хранения только массива
недостаточно. Однако деревья отрезков, способные вычислять сумму и максимум, можно реализовать с хранением двух массивов одинаковой длины и рекурсивной реализацией операции изменения.
Дерево отрезков для суммы (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.