Сведение задачи RMQ к задаче LCA

Постановка задачи RMQ

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

Алгоритм

Декартово дерево(Сartesian tree) на массиве [math]A[1..N][/math] - это бинарное дерево, рекурсивно определенное следующим образом:

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

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

Доказательство

Мы знаем что:

• 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок [math]A[i][/math] или [math]A[j][/math] меньше их самих.
• 2. Все вершины, которые лежат в дереве на пути от [math]A[i][/math] до [math]A[j][/math], а так же их поддеревья образуют подмассив [math]A[i..j][/math](возьмём только правое поддерево у [math]A[i][/math] и левое поддерево у [math]A[j][/math]). Т.к. всё, что левее [math]i[/math]-го элемента в массиве, лежит левее [math]A[i][/math] в дереве, и всё, что правее [math]j[/math]-го, лежит правее [math]A[j][/math]. A дерево содержит все элементы [math]A[1..N][/math].
• 3. Из всех вершин, определенных в п.2, [math]LCA(A[i], A[j])[/math] ближайший к корню и по п.1 имеет наименьшее значение в подмассиве [math]A[i..j][/math].

Сложность

Построение дерева наивным алгоритмом [math]O(n^2)[/math]. Существует алгоритм построение за [math]O(n)[/math]. Препроцессинг для [math]LCA[/math] - [math]O(n)[/math] и ответ на запрос [math]O(1)[/math]. В итоге получили [math]RMQ[/math] {построение [math]O(n)[/math], запрос [math]O(1)[/math]}.

См.также

• Сведение задачи LCA к задаче RMQ