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

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

2020-05-15T09:34:43Z

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

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

2020-05-15T09:32:42Z

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

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

2020-05-15T09:23:41Z

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

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

2020-05-15T09:21:35Z

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

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

2020-05-15T09:18:11Z

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

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

2020-05-15T09:06:35Z

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

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

2020-04-18T08:00:31Z

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

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

2020-04-09T05:09:58Z

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

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

2020-04-09T05:05:32Z

‎Задача RMQ.

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

2020-04-09T05:05:19Z

‎Задача RMQ.

@@ Строка 17: / Строка 17: @@
 == Как нам это поможет решить заявленную задачу? ==
 Рассмотрим вновь поступивший запрос 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>
 Таким образом, оценка доказана. <br><br>
 '''''Проблема'''''<br>
 С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.

@@ Строка 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>
 Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для 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>
 С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.

@@ Строка 11: / Строка 11: @@
 ...<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) обоснована.
 [[Файл:vis1.png]]

@@ Строка 11: / Строка 11: @@
 ...<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) обоснована.
-[[Файл:example.jpg]]
+[[Файл:vis1.png]]
 == Как нам это поможет решить заявленную задачу? ==

@@ Строка 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>
 В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
 == Как нам это поможет решить заявленную задачу? ==

@@ Строка 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>
 При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br>
 ...<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) обоснована.

@@ Строка 3: / Строка 3: @@
 '''''Формулировка проблемы.'''''<br>
-Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R). <br>
+Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R)". <br>
 == Идея решения ==