Сведение задачи RMQ к задаче LCA — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 4 участников)
Строка 1: Строка 1:
== Постановка задачи RMQ ==
+
{{Шаблон:Задача
[[Файл:Wiki.PNG|thumb|right|300x160px|Пример построенного дерева для массива А]]
+
|definition =Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
+
}}
 +
 
 
== Алгоритм ==
 
== Алгоритм ==
Декартово дерево (англ. ''сartesian tree'') по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
+
===Описание===
 +
[[Файл:Wiki.PNG|thumb|right|400x200px|Пример декартового дерева]]
 +
Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать  [[декартово дерево по неявному ключу]]. Тогда минимум на отрезке от <tex> i </tex> до <tex> j </tex> массива <tex> A </tex> будет равен наименьшему общему предку <tex>i</tex>-того и <tex>j</tex>-того элементов из декартова дерева, построенного на массиве <tex> A </tex>.
 +
 
 +
 
 +
Декартово дерево по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
 
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
 
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
 
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
 
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
Строка 11: Строка 17:
  
 
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 +
<br clear="all">
  
== Доказательство ==
+
=== Корректность ===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
<tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 
<tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 
|proof=
 
|proof=
Мы знаем что:
+
Положим <tex>w = LCA(A[i], A[j])</tex>.
* Любая вершина дерева всегда имеет меньшее или равное значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше или равен им самим.
+
 
* <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив <tex>A[i..j], </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и  <tex>A[j]</tex>. То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>
+
Заметим, что <tex>A[i]</tex> и <tex>A[j]</tex> не принадлежат одновременно либо правому, либо левому поддереву <tex>w</tex>, потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>w</tex>, и также являлся предком как <tex>A[i]</tex>, так и <tex>A[j]</tex>, что противоречит определению <tex>LCA</tex>. Из этого замечания следует, что <tex>w</tex> лежит между <tex>A[i]</tex> и <tex>A[j]</tex> и, следовательно, принадлежит отрезку <tex>A[i..j]</tex>.
 +
 
 +
 
 +
По построению мы также знаем, что:
 +
# Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.
 +
# Поддерево с корнем в <tex>w</tex> содержит в себе подмассив <tex>A[i..j]</tex>.
 +
 
 +
Суммируя, получаем, что <tex>w</tex> имеет минимальное значение на отрезке, покрывающем <tex>A[i..j]</tex>, и принадлежит отрезку <tex>A[i..j]</tex>, отсюда <tex>RMQ(i, j) = w</tex>.
 
}}
 
}}
== Построение дерева за линейное время ==
+
 
Пусть дан массив <tex>A[1..N]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение <tex>A[i]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину <tex>x</tex>, для которой <tex>x < A[i]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а <tex>A[i]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>O(n)</tex>.
+
=== Сложность ===
== Сложность ==
+
Существует [[Декартово дерево#Построение декартова дерева|алгоритм]], который строит декартово дерево за <tex>O(n)</tex>. Используя [[Сведение задачи LCA к задаче RMQ | алгоритм построения LCA]], получаем:
Выше описан алгоритм построения дерева за <tex>O(n)</tex>.
+
препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос {{---}} <tex>O(1)</tex>.  
Препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>.  
+
 
В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
+
Нам нужно единожды построить декартово дерево за <tex>O(n)</tex>, единожды провести препроцессинг за <tex>O(n)</tex> и отвечать на запросы за <tex>O(1)</tex>.
 +
 
 +
В итоге получили <tex>RMQ</tex> с построением за <tex>O(n)</tex> и ответом на запрос за <tex>O(1)</tex>.
 +
 
 
== См.также ==
 
== См.также ==
 
*[[Сведение задачи LCA к задаче RMQ]]
 
*[[Сведение задачи LCA к задаче RMQ]]
==Ссылки==
+
*[[Декартово дерево]]
*[http://e-maxx.ru/algo/rmq_linear Задача RMQ. Решение за O (1) с препроцессингом O (N)]
+
*[[Алгоритм Фарака-Колтона и Бендера]]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о наименьшем общем предке]]

Текущая версия на 19:36, 4 сентября 2022

Задача:
Дан массив [math]A[1..N][/math]. Поступают запросы вида [math](i, j)[/math], на каждый запрос требуется найти минимум в массиве [math]A[/math], начиная с позиции [math]i[/math] и заканчивая позицией [math]j[/math].


Алгоритм

Описание

Пример декартового дерева

Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать декартово дерево по неявному ключу. Тогда минимум на отрезке от [math] i [/math] до [math] j [/math] массива [math] A [/math] будет равен наименьшему общему предку [math]i[/math]-того и [math]j[/math]-того элементов из декартова дерева, построенного на массиве [math] A [/math].


Декартово дерево по неявному ключу на массиве [math]A[1..N][/math] — это бинарное дерево, допускающее следующее рекурсивное построение:

  • Корнем дерева является элемент массива, имеющий минимальное значение [math]A[/math], скажем [math]A[i][/math]. Если минимальных элементов несколько, можно взять любой.
  • Левым поддеревом является декартово дерево на массиве [math]A[1..i-1][/math].
  • Правым поддеревом является декартово дерево на массиве [math]A[i+1..N][/math].

Здесь и далее [math]A[i][/math] будет также использоваться для обозначения соответствующей вершины дерева.

Построим декартово дерево на массиве [math]A[/math]. Тогда [math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math].

Корректность

Теорема:
[math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math].
Доказательство:
[math]\triangleright[/math]

Положим [math]w = LCA(A[i], A[j])[/math].

Заметим, что [math]A[i][/math] и [math]A[j][/math] не принадлежат одновременно либо правому, либо левому поддереву [math]w[/math], потому как тогда бы соответствующий сын находился на большей глубине, чем [math]w[/math], и также являлся предком как [math]A[i][/math], так и [math]A[j][/math], что противоречит определению [math]LCA[/math]. Из этого замечания следует, что [math]w[/math] лежит между [math]A[i][/math] и [math]A[j][/math] и, следовательно, принадлежит отрезку [math]A[i..j][/math].


По построению мы также знаем, что:

  1. Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.
  2. Поддерево с корнем в [math]w[/math] содержит в себе подмассив [math]A[i..j][/math].
Суммируя, получаем, что [math]w[/math] имеет минимальное значение на отрезке, покрывающем [math]A[i..j][/math], и принадлежит отрезку [math]A[i..j][/math], отсюда [math]RMQ(i, j) = w[/math].
[math]\triangleleft[/math]

Сложность

Существует алгоритм, который строит декартово дерево за [math]O(n)[/math]. Используя алгоритм построения LCA, получаем: препроцессинг для [math]LCA[/math][math]O(n)[/math] и ответ на запрос — [math]O(1)[/math].

Нам нужно единожды построить декартово дерево за [math]O(n)[/math], единожды провести препроцессинг за [math]O(n)[/math] и отвечать на запросы за [math]O(1)[/math].

В итоге получили [math]RMQ[/math] с построением за [math]O(n)[/math] и ответом на запрос за [math]O(1)[/math].

См.также