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

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

2020-05-15T09:57:06Z

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

← Предыдущая версия		Версия от 09:57, 15 мая 2020
Строка 52:		Строка 52:
	Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>		Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>
	'''Способ 2.''' <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>

	''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''		''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

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

2020-05-15T09:56:55Z

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

← Предыдущая версия		Версия от 09:56, 15 мая 2020
Строка 52:		Строка 52:
	Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>		Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. <br><br>
	'''Способ 2.''' <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>

	''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''		''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

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

2020-05-15T09:53:28Z

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

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


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

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

2020-05-15T09:51:39Z

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

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


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

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

2020-05-15T09:49:31Z

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

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

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

2020-05-15T09:48:56Z

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

← Предыдущая версия		Версия от 09:48, 15 мая 2020
Строка 14:		Строка 14:
	1. TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. <br>		1. TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. <br>
	2. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>		2. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>
	3. TreeSeg ⋂ ~~QuerySe !=~~ ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.		3. TreeSeg ⋂ QuerySeg ≠ ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

	{{Template:Lemma		{{Template:Lemma

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

2020-05-15T09:48:06Z

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

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

	{{Template:Lemma		{{Template:Lemma

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

2020-05-15T09:46:45Z

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

← Предыдущая версия		Версия от 09:46, 15 мая 2020
Строка 13:		Строка 13:
	Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:<br>		Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:<br>
	1. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины. <br>		1. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины. <br>
	2. TreeSeg () QuerySeg = ~~(/)~~. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>		2. TreeSeg () QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать. <br>
	3. TreeSeg () QuerySe != ~~(/)~~. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.		3. TreeSeg () QuerySe != ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

	{{Template:Lemma		{{Template:Lemma
Строка 21:		Строка 21:
	\|Proof = Понятно, что оценка асимптотики алгоритма сводится к подсчету количества рекурсий, которые наша процедура потребует для выполнения. Рассмотрим произвольный уровень нашего дерева при запросе. На нем мы сделаем не более двух рекурсий вниз по дереву (случай 3). Таким образом, количество рекурсий ограничено O(1) * O(height) = O(log n).		\|Proof = Понятно, что оценка асимптотики алгоритма сводится к подсчету количества рекурсий, которые наша процедура потребует для выполнения. Рассмотрим произвольный уровень нашего дерева при запросе. На нем мы сделаем не более двух рекурсий вниз по дереву (случай 3). Таким образом, количество рекурсий ограничено O(1) * O(height) = O(log n).
	}}		}}


	== Изменение дерева ==		== Изменение дерева ==

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

2020-05-15T09:38:35Z

Структура

← Предыдущая версия		Версия от 09:38, 15 мая 2020
Строка 5:		Строка 5:

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


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

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

2020-04-08T18:20:34Z

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

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

	''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''		''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''