Sparse table - История изменений

Algocourselecturenotes: /* Как нам это поможет решить заявленную задачу? */

2020-05-15T09:34:43Z

Как нам это поможет решить заявленную задачу?

← Предыдущая версия		Версия от 09:34, 15 мая 2020
Строка 17:		Строка 17:
	== Как нам это поможет решить заявленную задачу? ==		== Как нам это поможет решить заявленную задачу? ==
	Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>		Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>
	[[Файл:vis2.png]]		[[Файл:vis2.png]]<br>
	Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>		Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>
	Таким образом, оценка доказана. <br><br>		Таким образом, оценка доказана. <br><br>
	'''''Проблема'''''<br>		'''''Проблема'''''<br>
	С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.		С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.

Algocourselecturenotes: /* Как нам это поможет решить заявленную задачу? */

2020-05-15T09:32:42Z

Как нам это поможет решить заявленную задачу?

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

	== Как нам это поможет решить заявленную задачу? ==		== Как нам это поможет решить заявленную задачу? ==
	Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны~~) (viz 10:20~~). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>		Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>
			[[Файл:vis2.png]]
	Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>		Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>
	Таким образом, оценка доказана. <br><br>		Таким образом, оценка доказана. <br><br>
	'''''Проблема'''''<br>		'''''Проблема'''''<br>
	С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.		С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.

Algocourselecturenotes: /* Идея решения */

2020-05-15T09:23:41Z

Идея решения

← Предыдущая версия		Версия от 09:23, 15 мая 2020
Строка 11:		Строка 11:
	...<br>		...<br>
	''Шаг k.'' <br>		''Шаг k.'' <br>
	Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (~~vis1~~). Таким образом, каждое такое значение мы посчитаем за O(1).<br>		Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге (иллюстрация ниже). Таким образом, каждое такое значение мы посчитаем за O(1).<br>
	В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.		В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
	[[Файл:vis1.png]]		[[Файл:vis1.png]]

Algocourselecturenotes: /* Идея решения */

2020-05-15T09:21:35Z

Идея решения

← Предыдущая версия		Версия от 09:21, 15 мая 2020
Строка 11:		Строка 11:
	...<br>		...<br>
	''Шаг k.'' <br>		''Шаг k.'' <br>
	Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (~~vis 7:45~~). Таким образом, каждое такое значение мы посчитаем за O(1).<br>		Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis1). Таким образом, каждое такое значение мы посчитаем за O(1).<br>
	В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.		В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
	[[Файл:~~example~~.~~jpg~~]]		[[Файл:vis1.png]]

	== Как нам это поможет решить заявленную задачу? ==		== Как нам это поможет решить заявленную задачу? ==

Algocourselecturenotes: /* Идея решения */

2020-05-15T09:18:11Z

Идея решения

← Предыдущая версия		Версия от 09:18, 15 мая 2020
Строка 13:		Строка 13:
	Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>		Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>
	В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.		В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
			[[Файл:example.jpg]]

	== Как нам это поможет решить заявленную задачу? ==		== Как нам это поможет решить заявленную задачу? ==

Algocourselecturenotes: /* Идея решения */

2020-05-15T09:06:35Z

Идея решения

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

	== Идея решения ==		== Идея решения ==
	Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n log n) чисел. <br>		Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i ∈ [0, n), k ∈ [0, log n]. Таким образом, у нас O(n log n) чисел. <br>
	''Шаг 0.'' <br>		''Шаг 0.'' <br>
	При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br>		При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br>
	...<br>		...<br>
	''Шаг k.'' <br>		''Шаг k.'' <br>
	Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>		Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>
	В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.		В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.

Algocourselecturenotes: /* Идея решения */

2020-04-18T08:00:31Z

Идея решения

← Предыдущая версия		Версия от 08:00, 18 апреля 2020
Строка 11:		Строка 11:
	...<br>		...<br>
	''Шаг k.'' <br>		''Шаг k.'' <br>
	Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>		Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br>
	В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.		В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.

Algocourselecturenotes: /* Как нам это поможет решить заявленную задачу? */

2020-04-09T05:09:58Z

Как нам это поможет решить заявленную задачу?

← Предыдущая версия		Версия от 05:09, 9 апреля 2020
Строка 16:		Строка 16:
	== Как нам это поможет решить заявленную задачу? ==		== Как нам это поможет решить заявленную задачу? ==
	Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны) (viz 10:20). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>		Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны) (viz 10:20). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br>
	Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (ф a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>		Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br>
	Таким образом, оценка доказана. <br><br>		Таким образом, оценка доказана. <br><br>
	'''''Проблема'''''<br>		'''''Проблема'''''<br>
	С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.		С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.

Algocourselecturenotes: /* Задача RMQ. */

2020-04-09T05:05:32Z

Задача RMQ.

← Предыдущая версия		Версия от 05:05, 9 апреля 2020
Строка 3:		Строка 3:

	'''''Формулировка проблемы.'''''<br>		'''''Формулировка проблемы.'''''<br>
	Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R). <br>		Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R)". <br>

	== Идея решения ==		== Идея решения ==

Algocourselecturenotes: /* Задача RMQ. */

2020-04-09T05:05:19Z

Задача RMQ.

← Предыдущая версия		Версия от 05:05, 9 апреля 2020
Строка 3:		Строка 3:

	'''''Формулировка проблемы.'''''<br>		'''''Формулировка проблемы.'''''<br>
	Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами от L ~~до R (не включая~~ R)". <br>		Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R). <br>

	== Идея решения ==		== Идея решения ==