data-structures => Дерево сегментов

Введение в сегментное дерево

Предположим, что у нас есть массив:

+-------+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| Value |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

Мы хотим выполнить некоторый запрос в этом массиве. Например:

Каков минимальный показатель от индекса- 2 до индекса- 4 ? -> 0
Каков максимум от индекса- 0 до индекса- 3 ? -> 4
Что такое суммирование из индекса- 1 в индекс- 5 ? -> 10

Как мы это узнаем?

Грубая сила:
Мы могли бы пройти массив от начального индекса до индекса окончания и ответить на наш запрос. В этом подходе каждый запрос принимает O(n) время, где n - разность между начальным индексом и индексом отделки. Но что, если есть миллионы номеров и миллионы запросов? Для m запросов это займет время O(mn) . Поэтому для значений 10⁵ в нашем массиве, если мы проводим 10 запросов, в худшем случае нам нужно пройти 10 единиц.

Динамическое программирование:
Мы можем создать матрицу 6X6 для хранения значений для разных диапазонов. Для минимального запроса диапазона (RMQ) наш массив будет выглядеть так:

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

Как только у нас будет эта матричная сборка, достаточно будет ответить на все RMQ. Здесь Matrix [i] [j] сохранит минимальное значение от index- i до index- j . Например: минимум от индекса- 2 до индекса- 4 - это матрица [2] [4] = 0 . Эта матрица отвечает на запрос в O(1) времени, но это занимает O (N²) время , чтобы построить эту матрицу и O(n²) пространство для его хранения. Поэтому, если n - действительно большое число, это не очень хорошо масштабируется.

Дерево сегментов:
Дерево сегментов представляет собой структуру данных дерева для хранения интервалов или сегментов. Он позволяет запрашивать, какой из сохраненных сегментов содержит заданную точку. Это занимает O(n) время для построения дерева сегмента, он занимает O(n) пространства , чтобы поддерживать его , и он отвечает на запрос в O(logn) время.

Дерево сегментов - это двоичное дерево, а элементы данного массива будут листами этого дерева. Мы создадим дерево сегментов, разделив массив пополам, пока не достигнем одного элемента. Поэтому наше подразделение предоставило бы нам:

Теперь, если мы заменим нелистовые узлы минимальным значением их листьев, получим:

Итак, это наше дерево сегментов. Мы можем заметить, что корневой узел содержит минимальное значение всего массива (диапазон [0,5]), его левый ребенок содержит минимальное значение нашего левого массива (диапазон [0,2]), правый ребенок содержит минимум значение нашего правого массива (диапазон [3,5]) и т. д. Листовые узлы содержат минимальное значение каждой отдельной точки. Мы получаем:

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

Частичное перекрытие: мы проверяем оба листа.
Общее перекрытие: мы возвращаем значение, хранящееся в узле.
No Overlap: Мы возвращаем очень большое значение или бесконечность.

Скажем, мы хотим проверить диапазон [2,4] , это означает, что мы хотим найти минимум от индекса- 2 до 4 . Мы начнем с корня и проверим, перекрывает ли диапазон наших узлов наш диапазон запросов или нет. Вот,

[2,4] не перекрывается полностью [0,5] . Поэтому мы проверим оба направления.
- В левом поддереве [2,4] частично перекрываются [0,2] . Мы проверим оба направления.
  - В левом поддереве [2,4] не перекрывается [0,1] , поэтому это не будет способствовать нашему ответу. Мы возвращаемся бесконечно .
  - В правом поддереве [2,4] полностью перекрывается [2,2] . Мы возвращаемся 4 .
    Минимум этих двух возвращаемых значений (4, бесконечность) равен 4 . Мы получаем 4 из этой части.
- В правом поддереве [2,4] частично перекрывается. Поэтому мы проверим оба направления.
  - В левом поддереве [2,4] полностью перекрывается [3,4] . Мы возвращаем 0 .
  - В правом поддереве [2,4] не перекрывается [5,5] . Мы возвращаемся бесконечно .
    Минимум этих двух возвращаемых значений (0, бесконечность) равен 0 . Из этой части получаем 0 .
Минимум возвращаемых значений (4,0) равен 0 . Это наш желаемый минимум в диапазоне [2,4] .

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

Использование:

Минимальный запрос диапазона
Самый низкий общий предок
Леновое распространение
Динамическая сумма субтитров
Пренебрежение и мин.
Двойные поля
Поиск k-го наименьшего элемента
Поиск количества неупорядоченных пар

Реализация дерева сегментов с использованием массива

Скажем, у нас есть массив: Item = {-1, 0, 3, 6} . Мы хотим построить массив SegmentTree, чтобы узнать минимальное значение в заданном диапазоне. Дерево нашего сегмента будет выглядеть так:

Числа под узлами показывают индексы всех значений, которые мы будем хранить в нашем массиве SegmentTree . Мы видим, что для хранения 4 элементов нам нужен массив размером 7. Это значение определяется:

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

Поэтому, если бы у нас был массив длиной 5, размер нашего массива SegmentTree был бы: ( 8 * 2 ) - 1 = 15 . Теперь, чтобы определить положение левого и правого дочерних узлов узла, если узел находится в индексе i , тогда его позиция:

Левый ребенок обозначается: (2 * i) + 1 .
Право ребенка обозначается: (2 * i) + 2 .

И индекс родителя любого узла в индексе i может быть определен: (i - 1) / 2 .

Таким образом, массив SegmentTree, представляющий наш пример, будет выглядеть так:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  3  |  -1 |  0  |  3  |  6  |
+-----+-----+-----+-----+-----+-----+-----+

Давайте рассмотрим псевдокод для построения этого массива:

Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
    SegmentTree[position] := Item[low]
else
    mid := (low+high)/2
    constructTree(Item, SegmentTree, low, mid, 2*position+1)
    constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
    SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if

Сначала мы вводим значения и инициализируем массив SegmentTree с infinity используя длину массива Item как его размер. Мы называем процедуру следующим образом:

low = Начальный индекс массива Item .
high = Конечный индекс массива Item .
position = 0, указывает корень нашего Дерева сегментов.

Теперь давайте попробуем понять процедуру, используя пример:

Размер нашего массива Item равен 4 . Мы создаем массив длины (4 * 2) - 1 = 7 и инициализируем их с infinity . Вы можете использовать для этого очень большое значение. Наш массив будет выглядеть так:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Поскольку это рекурсивная процедура, мы увидим операцию ConstructTree используя таблицу рекурсии, которая отслеживает low , high , position , mid и calling line при каждом вызове. Сначала мы вызываем ConstructTree (Item, SegmentTree, 0, 3, 0) . Здесь low не такой же high , мы получим mid . calling line указывает, какой ConstructTree вызывается после этого оператора. Обозначим ConstructTree внутри процедуры как 1 и 2 соответственно. Наша таблица будет выглядеть так:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

Поэтому, когда мы называем ConstructTree-1 , мы передаем: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . Одна вещь, которую вы можете заметить, то есть 2*position+1 - левый дочерний корень , который равен 1 . Поскольку low не равен high , мы получаем mid . Наша таблица будет выглядеть так:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

В следующем рекурсивном вызове мы получаем low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Снова левый ребенок индекса 1 равен 3 . Здесь low high , поэтому мы устанавливаем SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Наш массив SegmentTree будет выглядеть так:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Наша таблица рекурсии будет выглядеть так:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

Таким образом, вы можете видеть, -1 имеет правильное положение. Поскольку этот рекурсивный вызов завершен, мы возвращаемся к предыдущей строке нашей таблицы рекурсии. Стол:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

В нашей процедуре мы выполняем вызов ConstructTree-2 . На этот раз мы проходим low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Наша calling line меняется на 2 . Мы получаем:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

Так как low равно high , мы устанавливаем: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Наш массив SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Наша таблица рекурсии:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

Снова вы можете видеть, 2 имеет свое правильное положение. После этого рекурсивного вызова мы вернемся к предыдущей строке нашей таблицы рекурсии. Мы получаем:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

Мы выполняем последнюю строку нашей процедуры, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Наш массив SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Поскольку этот вызов рекурсии завершен, мы возвращаемся к предыдущей строке нашей таблицы рекурсии и вызываем ConstructTree-2 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

Мы видим, что левая часть нашего дерева сегментов завершена. Если мы продолжим таким образом, после завершения всей процедуры мы, наконец, получим завершенный массив SegmentTree , который будет выглядеть так:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Сложность времени и пространства для построения этого массива SegmentTree : O(n) , где n обозначает количество элементов в массиве Item . Настроенный массив SegmentTree можно использовать для выполнения Минимального запроса диапазона (RMQ) . Чтобы построить массив для выполнения Range Maximum Query , нам нужно заменить строку:

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

с:

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])

Выполнение минимального запроса диапазона

Процедура выполнения RMQ уже показана во введении. Псевдокод для проверки Минимального запроса диапазона будет:

Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high        //Total Overlap
    Return SegmentTree[position]
else if qLow > high || qHigh < low      //No Overlap
    Return infinity
else                                    //Partial Overlap
    mid := (low+high)/2
    Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if

Здесь qLow = The lower range of our query , qHigh = The upper range of our query . low = starting index of Item array , high = Finishing index of Item array , position = root = 0 . Теперь попробуем разобраться в процедуре, используя пример, который мы создали ранее:

Наш массив SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Мы хотим найти минимум в диапазоне [1,3] .
Поскольку это рекурсивная процедура, мы увидим операцию RangeMinimumQuery используя таблицу рекурсии, которая отслеживает qLow , qHigh , low , high , position , mid и calling line . Сначала мы называем RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Здесь первые два условия не выполняются (частичное перекрытие). Мы получим mid . calling line указывает, какой RangeMinimumQuery вызывается после этого Мы RangeMinimumQuery вызовы RangeMinimumQuery внутри процедуры RangeMinimumQuery 1 и 2. Наша таблица будет выглядеть так:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Поэтому, когда мы вызываем RangeMinimumQuery-1 , мы передаем: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . Одна вещь, которую вы можете заметить, то есть 2*position+1 - левый дочерний узел . Это означает, что мы проверяем левый дочерний корень . Поскольку [1,3] частично перекрываются [0,1] , первые два условия не выполняются, мы получаем mid . Наша таблица:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

В следующем рекурсивном вызове мы пропускаем low = 0 , high = mid = 0 , position = 2*position+1 = 3 . Мы достигаем самого левого листа нашего дерева. Поскольку [1,3] не перекрывается с [0,0] , мы возвращаем infinity к нашей вызывающей функции. Таблица рекурсии:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   0  |     3    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Поскольку этот рекурсивный вызов завершен, мы возвращаемся к предыдущей строке нашей таблицы рекурсии. Мы получаем:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

В нашей процедуре мы выполняем RangeMinimumQuery-2 . На этот раз мы проходим low = mid+1 = 1 , high = 1 и position = 2*position+2 = 4 . Наша calling line changes to **2** . Мы получаем:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       2      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  1  |   1  |     4    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Итак, мы идем к правильному ребру предыдущего узла. На этот раз происходит полное совпадение. Мы возвращаем значение SegmentTree[position] = SegmentTree[4] = 2 .

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

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

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Мы закончили смотреть на левую часть нашего дерева сегментов. Теперь мы будем называть RangeMinimumQuery-2 отсюда. Мы пройдем low = mid+1 = 1+1 =2 , high = 3 и position = 2*position+2 = 2 . Наша таблица:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  2  |   3  |     2    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Существует полное совпадение. Поэтому мы возвращаем значение: SegmentTree[position] = SegmentTree[2] = 0 . Мы возвращаемся к рекурсии, из которой были вызваны эти двое детей, и получить минимум (4,0) , то есть 0 и вернуть значение.

После выполнения процедуры получаем 0 , что является минимумом от индекса- 1 до индекса- 3 .

Сложность выполнения для этой процедуры - O(logn) где n - количество элементов в массиве Items . Чтобы выполнить Максимальный запрос диапазона, нам нужно заменить строку:

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

с:

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

Леновое распространение

Предположим, вы уже создали дерево сегментов. Вы должны обновить значения массива, это не только изменит листовые узлы вашего дерева сегментов, но и минимальное / максимальное количество в некоторых узлах. Давайте посмотрим на это с примера:

Это наше минимальное дерево сегментов из 8 элементов. Чтобы дать вам быстрое напоминание, каждый узел представляет собой минимальное значение диапазона, упомянутого рядом с ним. Скажем, мы хотим увеличить значение первого элемента нашего массива на 3 . Как мы можем сделать это? Мы будем следить за тем, как мы проводили RMQ. Процесс будет выглядеть так:

Сначала мы проходим корень. [0,0] частично перекрываются с [0,7] , мы идем в оба направления.
- В левом поддереве [0,0] частично перекрывается с [0,3] , мы идем в оба направления.
  - В левом поддереве [0,0] частично перекрывается с [0,1] , мы идем в оба направления.
    - В левом поддереве [0,0] полностью перекрывается с [0,0] , а с его листового узла мы обновляем узел, увеличивая его значение на 3 . И верните значение -1 + 3 = 2 .
    - В правом поддереве [1,1] не перекрывается с [0,0] , мы возвращаем значение в узле ( 2 ).
      Минимальное количество этих двух возвращаемых значений ( 2 , 2 ) равно 2 , поэтому мы обновляем значение текущего узла и возвращаем его.
  - В правом поддереве [2,3] не перекрывается с [0,0] , мы возвращаем значение узла. ( 1 ).
    Поскольку минимум этих двух возвращаемых значений ( 2 , 1 ) равен 1 , мы обновляем значение текущего узла и возвращаем его.
- В правом поддереве [4,7] не перекрывается с [0,0] , мы возвращаем значение узла. ( 1 ).
Наконец, значение корневого узла обновляется, поскольку минимум двух возвращаемых значений (1,1) равен 1 .

Мы видим, что для обновления одного узла требуется сложность времени O(logn) , где n - количество листовых узлов. Поэтому, если нас попросят обновить некоторые узлы от i до j , нам потребуется сложность времени O(nlogn) . Это становится громоздким при большом значении n . Давайте будем ленивыми, т. Е. Работаем только тогда, когда это необходимо. Как? Когда нам нужно обновить интервал, мы обновим узел и отметьте его дочерний элемент, который необходимо обновить, и при необходимости обновим его. Для этого нам нужен массив ленивый того же размера, что и дерево сегментов. Первоначально все элементы ленивого массива будут равны 0, представляющие отсутствие ожидающего обновления. Если в lazy [i] есть ненулевой элемент, тогда этот элемент должен обновить узел i в дереве сегментов, прежде чем делать какие-либо операции с запросами. Как мы это сделаем? Давайте посмотрим на пример:

Скажем, для нашего дерева примеров мы хотим выполнить некоторые запросы. Это:

приращение [0,3] на 3 .
приращение [0,3] на 1 .
приращение [0,0] на 2 .

приращение [0,3] на 3:

Мы начинаем с корневого узла. Сначала мы проверяем, соответствует ли это значение. Для этого мы проверяем наш ленивый массив, который равен 0 , это означает, что значение является актуальным. [0,3] частично перекрываются [0,7] . Поэтому мы идем к обоим направлениям.
- В левом поддереве нет ожидающего обновления. [0,3] полностью перекрываются [0,3] . Поэтому мы обновляем значение узла на 3 . Таким образом, значение становится равным -1 + 3 = 2 . На этот раз мы не собираемся идти полностью. Вместо того, чтобы спускаться, мы обновляем соответствующий ребенок в ленивом дереве нашего текущего узла и увеличиваем их на 3 . Мы также возвращаем значение текущего узла.
- В правом поддереве нет ожидающего обновления. [0,3] не перекрывается [4,7] . Поэтому мы возвращаем значение текущего узла (1) .
  Минимум двух возвращаемых значений ( 2 , 1 ) равно 1 . Мы обновляем корневой узел до 1 .

Дерево сегментов и Lazy Tree будет выглядеть так:

Ненулевые значения в узлах нашего Lazy Tree представляют, в этих узлах и ниже есть обновления. Мы обновим их, если потребуется. Если нас спросят, каков минимум в диапазоне [0,3] , мы перейдем к левому поддереву корневого узла и, поскольку нет ожидающих обновлений, мы вернем 2 , что верно. Таким образом, этот процесс не влияет на правильность алгоритма дерева сегментов.

приращение [0,3] на 1:

Мы начинаем с корневого узла. Нет ожидающего обновления. [0,3] частично перекрываются [0,7] . Поэтому мы идем в оба направления.
- В левом поддереве нет ожидающего обновления. [0,3] полностью перекрываются [0,3] . Мы обновляем текущий узел: 2 + 1 = 3 . Поскольку это внутренний узел, мы обновляем его дочерние элементы в Lazy Tree, чтобы увеличить его на 1 . Мы также вернем значение текущего узла ( 3 ).
- В правом поддереве нет ожидающего обновления. [0,3] не перекрывается [4,7] . Мы возвращаем значение текущего узла ( 1 ).
Мы обновляем корневой узел, беря минимум два возвращаемых значения ( 3 , 1 ).

Дерево сегментов и Lazy Tree будет выглядеть так:

Как вы можете видеть, мы накапливаем обновления на Lazy Tree, но не толкаем их. Это то, что означает «Ленивое размножение». Если бы мы не использовали его, мы должны были подталкивать значения до листьев, что стоило бы нам более ненужной временной сложности.

приращение [0,0] на 2:

Мы начинаем с корневого узла. Поскольку корень обновлен и [0,0] частично перекрываются [0,7] , мы переходим в оба направления.
- В левом поддереве текущий узел обновлен и [0,0] частично перекрывает [0,3] , мы идем в оба направления.
  - В левом поддереве текущий узел в Lazy Tree имеет ненулевое значение. Итак, есть обновление, которое еще не было распространено на этом узле. Мы собираемся сначала обновить этот узел в нашем Дереве сегментов. Таким образом, это становится равным -1 + 4 = 3 . Затем мы будем распространять это 4 на своих детей в «Ленивом дереве». Поскольку мы уже обновили текущий узел, мы изменим значение текущего узла в Lazy Tree на 0 . Затем [0,0] частично перекрывает [0,1] , поэтому мы идем в оба направления.
    - В левом узле значение необходимо обновить, поскольку в текущем узле Lazy Tree имеется ненулевое значение. Поэтому мы обновляем значение до -1 + 4 = 3 . Теперь, поскольку [0,0] полностью перекрывает [0,0] , мы обновляем значение текущего узла до 3 + 2 = 5 . Это листовой узел, поэтому нам больше не нужно распространять значение. Мы обновляем соответствующий узел в Lazy Tree до 0, поскольку все значения распространяются до этого узла. Мы возвращаем значение текущего узла ( 5 ).
    - На нужном узле значение необходимо обновить. Таким образом, значение становится: 4 + 2 = 6 . Поскольку [0,0] не перекрывается [1,1] , мы возвращаем значение текущего узла ( 6 ). Мы также обновляем значение в Lazy Tree до 0 . Не требуется распространения, так как это листовой узел.
      Мы обновляем текущий узел, используя минимум два возвращаемых значения ( 5 , 6 ). Мы возвращаем значение текущего узла ( 5 ).
  - В правом поддереве есть ожидающее обновления. Мы обновляем значение узла до 1 + 4 = 5 . Поскольку это не листовой узел, мы передаем значение своим дочерним элементам в нашем Lazy Tree и обновляем текущий узел до 0 . Поскольку [0,0] не перекрывается с [2,3] , мы возвращаем значение нашего текущего узла ( 5 ).
    Мы обновляем текущий узел, используя минимум возвращаемых значений ( 5 , 5 ) и возвращаем значение ( 5 ).
- В правом поддереве нет ожидающего обновления, и поскольку [0,0] не перекрывается [4,7] , мы возвращаем значение текущего узла ( 1 ).
Мы обновляем корневой узел, используя минимум двух возвращаемых значений ( 5 , 1 ).

Дерево сегментов и Lazy Tree будет выглядеть так:

Мы можем заметить, что значение в [0,0] при необходимости получило все приращение.

Теперь, если вас попросят найти минимум в диапазоне [3,5] , если вы поняли до этого момента, вы можете легко выяснить, как будет идти запрос, а возвращаемое значение будет равно 1 . Наш сегмент Tree и Lazy Tree будет выглядеть так:

Мы просто следовали тому же процессу, который мы выполнили при поиске RMQ с дополнительными ограничениями проверки Lazy Tree для ожидающих обновлений.

Другое дело, что мы можем сделать, вместо того, чтобы возвращать значения из каждого узла, поскольку мы знаем, что будет дочерним узлом нашего текущего узла, мы можем просто проверить их, чтобы найти минимум этих двух.

Псевдокодом для обновления в Lazy Propagation будет:

Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, high, position):
if low > high                                                //out of bounds
    Return
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    LazyTree[position] := 0
end if
if startRange > low or endRange < high                       //doesn't overlap
    Return
end if
if startRange <= low && endRange >= high                     //total overlap
    segmentTree[position] := segmentTree[position] + delta
    if low is not equal to high
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1], 
                                                    segmentTree[2 * position + 2])

И псевдокод для RMQ в Lazy Propagation будет:

Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
    Return infinity
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high
        segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
    end if
    LazyTree[position] := 0
end if
if qLow > high and qHigh < low                                //no overlap
    Return infinity
end if
if qLow <= low and qHigh >= high                              //total overlap
    Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, 
                                        low, mid, 2 * position + 1),
           RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
                                        mid + 1, high, 2 * position + 1)

Modified text is an extract of the original Stack Overflow Documentation

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow

data-structures
Дерево сегментов

Поиск…

Введение в сегментное дерево

Реализация дерева сегментов с использованием массива

Выполнение минимального запроса диапазона

Леновое распространение