74
правки
Изменения
Нет описания правки
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;,* коммутативности: $a \circ b = b \circ a$;,
* идемпотентности: $a \circ a = a $.
$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=
Отрезок $(a_{r-k}, a_k)$ содержится в обои обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
}}
</wikitex>
== Применение к задаче RMQ ==
<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>\lfloor \log_2l \rfloor</tex>. Для этого введем функцию <tex>fl</tex>(от ''floor'', т.к. логарифм округляется вниз):
'''int''' '''fl'''('''int''' len):
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]
* [[ Heavy-light декомпозиция | Heavy-light декомпозиция]]
== Источники информации==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
