Введение в деревья сегментов — учебные пособия по структуре данных и алгоритмам

Что такое дерево сегментов?

Дерево сегментов — это структура данных, в узлах которой хранится информация о ряде элементов. Это также позволяет пользователям изменять массив и выполнять запросы диапазона с меньшей сложностью. Например, мы можем выполнить суммирование диапазона массива между диапазоном от L до R, а также изменить массив от диапазона от L до R с временной сложностью log(N) .

Виды операций:

Операции, которые может выполнять дерево сегментов, должны быть бинарными и ассоциативными . В целом значения должны принадлежать множеству полугруппы. Нейтральный элемент должен быть очевиден в зависимости от типа операции и полугруппы, которые мы ищем. Например, если мы хотим найти сумму по диапазону значений в массиве, где элементы принадлежат тогда нейтральный элемент в этом случае будет равен 0. Вот некоторые примеры операций:

• Сложение/вычитание
• Максимум/минимум
• НОД/МОК

Структура дерева

Дерево сегментов работает по принципу «разделяй и властвуй».

• На каждом уровне мы делим сегменты массива на две части. Если данный массив имел [0, . . ., N-1] элементов в нем, то две части массива будут [0, . . ., N/2-1] и [N/2, . . ., N-1] .
• Затем мы будем рекурсивно продолжать, пока нижняя и верхняя границы диапазона не станут равными.
• Структура дерева сегментов похожа на бинарное дерево.

Дерево сегментов обычно представляется с помощью массива, где первое значение хранит значение для всего диапазона массива, а дочерний элемент узла с i- ^м индексом находится в (2*i + 1) и (2*i + 2) .

Построение дерева сегментов:

При построении дерева сегментов необходимо учитывать два важных момента:

• Choosing what value to be stored in the nodes according to the problem definition
• What should the merge operation do

Если в определении задачи указано, что нам нужно вычислить сумму по диапазонам, то значение в узлах должно хранить сумму значений по диапазонам.

• Значения дочернего узла объединяются обратно с родительским узлом для хранения значения для этого конкретного диапазона [т. е. диапазона, охватываемого всеми узлами его поддерева].
• В конце концов, листовые узлы хранят информацию об одном элементе. Все листовые узлы хранят массив, на основе которого строится дерево сегментов.

Ниже приведены шаги для построения дерева сегментов:

1. Начните с листьев дерева
2. Рекурсивно построить родителей из операции слияния

Операция слияния займет постоянное время, если оператор занимает постоянное время. SO построение всего дерева занимает O (N) времени.

Запрос диапазона

Разберемся в этом с помощью следующей задачи

Given two integers L and R return the sum of the segment [L, R]

Первым шагом является построение дерева отрезков с оператором сложения и 0 в качестве нейтрального элемента.

• Если диапазон является одним из значений диапазона узла, просто верните ответ.
• В противном случае нам нужно будет пройти по левому и правому дочерним элементам узлов и рекурсивно продолжить процесс, пока мы не найдем узел, который покрывает диапазон, который полностью покрывает часть или весь диапазон [L, R].
• При возврате с каждого вызова нам нужно объединить ответы, полученные от каждого его дочернего элемента.

Поскольку высота дерева сегментов равна logN, время запроса будет O(logN) на запрос.

Обновления точек

Given an index,  idx, update the value of the array at index idx with value V

Вклад элемента заключается только в пути от его листа к его родителю. Таким образом, обновление затронет только элементы logN .

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

Временная сложность будет O(logN) .

Ниже представлена реализация построения , запроса и обновления точек для дерева отрезков:

Временная сложность: O(N)

• Операция по строительству занимает O(N) времени
• Операция запроса занимает O(logN) времени
• Каждое обновление выполняется за время O(logN)

Вспомогательное пространство: O(n)

Обновление интервала (ленивое распространение):

Ленивое распространение: метод ускорения обновления диапазона

• Мы можем отложить некоторые обновления (избежать рекурсивных вызовов в update) и делать такие обновления только при необходимости, когда есть несколько обновлений и обновления выполняются для диапазона.
• Узел в дереве сегментов хранит или отображает результаты запроса для различных индексов.
• Кроме того, все потомки узла также должны быть обновлены, если диапазон операции обновления включает этот узел.
  • В качестве примера возьмем узел со значением 27 на картинке выше. Этот узел содержит сумму значений с индексами от 3 до 5. Этот узел и все его потомки должны быть обновлены, если наш запрос на обновление охватывает диапазон от 2 до 5.
  • Сохраняя эту информацию об обновлении в отдельных узлах, называемых ленивыми узлами или значениями, мы используем ленивое распространение для обновления только узла со значением 27 и задержки обновлений для его потомков.
• Мы создаем массив с именем lazy[] для замены ленивого узла. Размер lazy[] такой же, как массив, используемый для представления дерева сегментов в следующем коде, то есть tree[] .
• Цель состоит в том, чтобы установить все lazy[elements] в 0.
  • В узле дерева сегментов i нет ожидающих изменений, если lazy[i] имеет значение 0.
  • Ненулевое значение для lazy[i] указывает, что перед выполнением каких-либо запросов к узлу i в дереве сегментов эту сумму необходимо добавить к узлу.

Ниже приведена реализация, демонстрирующая работу отложенного распространения.

Временная сложность: O(N)
Вспомогательное пространство: O(MAX)