Редактирование: Решение RMQ с помощью разреженной таблицы

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 12: Строка 12:
 
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
 
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
  
Простой метод построения таблицы заключён в следующем рекуррентном соотношении:
+
Простой метод построения таблицы заключён в следующем реккурентном соотношении:  
$$
+
<wikitex>$$ST[i][j]=
ST[i][j]=
 
 
\begin{cases}
 
\begin{cases}
 
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right),&\text{если $j > 0$;}\\
 
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right),&\text{если $j > 0$;}\\
Строка 20: Строка 19:
 
\end{cases}
 
\end{cases}
 
$$
 
$$
 
+
</wikitex>
 
== Идемпотентность ==
 
== Идемпотентность ==
 
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.  
 
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.  
 
+
<wikitex>
 
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
 
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
 
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $,
 
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $,
Строка 32: Строка 31:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
$a_l \circ a_{l+1} \circ \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $\frac{r - l}{2} \leqslant k \leqslant  r - l$.
+
$a_l \circ a_{l+1} \circ \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $l \leqslant k \leqslant  r$.
 
|proof=
 
|proof=
Отрезок $(a_{r-k}, a_{l + k})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
+
Отрезок $(a_{r-k}, a_k)$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
 
}}
 
}}
 +
</wikitex>
  
 
== Применение к задаче RMQ ==
 
== Применение к задаче RMQ ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: