Дерево отрезков - История изменений

Algocourselecturenotes: /* Пример задачи */

2020-05-15T09:57:06Z

‎Пример задачи

Algocourselecturenotes: /* Пример задачи */

2020-05-15T09:56:55Z

‎Пример задачи

Algocourselecturenotes: /* Персистентное дерево отрезков */

2020-05-15T09:53:28Z

‎Персистентное дерево отрезков

Algocourselecturenotes: /* Изменение элементов на подотрезке */

2020-05-15T09:51:39Z

‎Изменение элементов на подотрезке

Algocourselecturenotes: /* Обработка запроса */

2020-05-15T09:49:31Z

‎Обработка запроса

Algocourselecturenotes: /* Обработка запроса */

2020-05-15T09:48:56Z

‎Обработка запроса

Algocourselecturenotes: /* Обработка запроса */

2020-05-15T09:48:06Z

‎Обработка запроса

Algocourselecturenotes: /* Обработка запроса */

2020-05-15T09:46:45Z

‎Обработка запроса

Algocourselecturenotes: /* Структура */

2020-05-15T09:38:35Z

‎Структура

Algocourselecturenotes: /* Пример задачи */

2020-04-08T18:20:34Z

‎Пример задачи

@@ Строка 52: / Строка 52: @@
 Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>
 '''Способ 2.''' <br>
-Отсортируем элементы по возрастанию (разумеется, с сохранением первоначальной позиции элементов), получив массив S. Создадим пустой массив того же размера E, сделаем на нем дерево отрезков. После этого будем пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого достаточно сделать count (L, R, "≤y") - count (L, R, "<x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая.<br><br>
+Отсортируем элементы по возрастанию (разумеется, с сохранением первоначальной позиции элементов), получив массив S. Создадим пустой массив того же размера E, сделаем на нем дерево отрезков. После этого будем пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого достаточно сделать count (L, R, "≤ y") - count (L, R, "< x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая.<br><br>
 ''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

@@ Строка 52: / Строка 52: @@
 Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>
 '''Способ 2.''' <br>
-Отсортирую элементы по возрастанию (разумеется, с сохранением первоначальной позиции), получив массив S. Создам пустой массив того же размера E, сделаю на нем дерево отрезков. После этого буду пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого мне достаточно сделать count (L, R, "<=y") - count (L, R, "<x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая.<br><br>
+Отсортируем элементы по возрастанию (разумеется, с сохранением первоначальной позиции элементов), получив массив S. Создадим пустой массив того же размера E, сделаем на нем дерево отрезков. После этого будем пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого достаточно сделать count (L, R, "≤y") - count (L, R, "<x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая.<br><br>
 ''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

@@ Строка 40: / Строка 40: @@
 ''Замечание: здесь нам придется отказаться от идеи хранить структуру в виде массива, по аналогии с бинарной кучей.''<br><br>
 Вдобавок к уже известным функциям и требованием иногда хочется уметь возвращаться к старой версии дерева. Таким образом, мы хотим добавить функцию checkout (version_number), где version_number - количество вызовов функции изменения дерева на подотрезке.<br>
-Заметим, что при каждом вызове функции изменения дерева на подотрезке изменяется лишь O(log n) вершин. (vis 56:46). Более того, при каждой такой операции изменяется лишь один путь от  корня до листа. Итак, мы может создавать новую версию этого пути, возвращая из функции change указатель на новую версию того самого пути. Тогда в каждой вершине на этом пути один из детей будет обновленным, а другой старым.<br><br>
+Заметим, что при каждом вызове функции изменения дерева на подотрезке изменяется лишь O(log n) вершин.
 Имея на руках систему контроля версий, мы можем считать нашу функцию f от полуинтервала исходного массива не только в актуальной версии дерева, но и в любой его версии, имея массив, в котором индекс - номер версии, а значение - соответствующая подветвь.
 == Пример задачи ==

@@ Строка 35: / Строка 35: @@
 == Изменение элементов на подотрезке ==
 Пусть нам поступает запрос на присвоение всем элементам с индексами от L до R значения new_value. Вновь применим идею отложенной операции. Будем рекурсивно спускаться от корня пока весь соответствующий текущей вершине полуинтервал не будет лежать в [L, R); когда это произошло, сохраним в этой вершине запрос на изменение. <br>
-Тогда нужно понять, как это повлияет на процедуру  обработки запроса. Разумеется, изменится случай 1 - сейчас нам придется учитывать не только значение вершины, но и эту отложенную операцию, что, впрочем, несильно усложняет дело. Также необходимо в случае 3 "протолкнуть" отложенную операцию в сыновей. Понятно, что никакую асимптотику это нарушить не может. Но здесь важно не забыть после рассмотрения случаев 1, 2, 3 обновить значение в текущей вершине на основе обновленной информации о детях и той ленивой метке, которая сейчас есть. И только после этого можно безопасно возвращаться на уровень выше.
+Тогда нужно понять, как это повлияет на процедуру  обработки запроса. Разумеется, изменится случай 1 - сейчас нам придется учитывать не только значение вершины, но и эту отложенную операцию, что, впрочем, несильно усложняет дело. Также необходимо в случае 3 "протолкнуть" отложенную операцию в сыновей. Понятно, что никакую асимптотику это нарушить не может. Но здесь важно не забыть после рассмотрения случаев 1, 2, 3 обновить значение в текущей вершине на основе вновь полученной информации о листьях данной вершины. И только после этого можно безопасно возвращаться к родительскому узлу.
 == Персистентное дерево отрезков ==

@@ Строка 13: / Строка 13: @@
 Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:<br>
 . TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. <br>
-. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>
+. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящая вершина" думала над тем, что с этим знанием делать. <br>
 . TreeSeg ⋂ QuerySeg ≠ ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

@@ Строка 12: / Строка 12: @@
 == Обработка запроса ==
 Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:<br>
-. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины. <br>
+. TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. <br>
-. TreeSeg () QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>
+. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>
-. TreeSeg () QuerySe != ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.
+. TreeSeg ⋂ QuerySe != ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.
 {{Template:Lemma

@@ Строка 5: / Строка 5: @@
 == Структура ==
-На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)<br>
+На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки.
 Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n). <br>
 == Обработка запроса ==