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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 32: Строка 32:
 
{{Утверждение
 
{{Утверждение
 
|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)$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
 
}}
 
}}
  

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

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

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

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