Розв'язання RMQ (запиту мінімуму на відрізку) через пошук LCA (найнижчого спільного предка)

Задано масив A[0..N-1]. Для кожного запиту виду [L, R] ми хочемо знайти мінімум у масиві A, починаючи з позиції L і закінчуючи позицією R. Ми вважатимемо, що масив A не змінюється в процесі, тобто ця стаття описує розв'язок статичної задачі RMQ.

Нижче наведено опис асимптотично оптимального розв'язку. Він стоїть осторонь від інших розв'язків задачі RMQ, оскільки дуже від них відрізняється: він зводить задачу RMQ до задачі LCA, а потім використовує алгоритм Фараха-Колтона і Бендера, який зводить задачу LCA назад до спеціалізованої задачі RMQ і розв'язує її.

Коли підходить цей алгоритм?

• Потрібен мінімум на відрізку при $O(N)$ передобробці та $O(1)$ на запит, а масив не змінюється? (якщо $O(N \log N)$ передобробки прийнятна — простіше взяти розріджену таблицю)
• Елементи масиву оновлюються між запитами? Тоді цей метод не підходить — потрібне дерево відрізків.

Алгоритм

Ми будуємо декартове дерево з масиву A. Декартове дерево масиву A — це двійкове дерево з властивістю min-купи (значення батьківської вершини має бути меншим або рівним значенню її дітей), таке, що симетричний обхід (in-order) дерева відвідує вершини в тому самому порядку, у якому вони стоять у масиві A.

Іншими словами, декартове дерево — це рекурсивна структура даних. Масив A буде розбито на 3 частини: префікс масиву до мінімуму, сам мінімум і решта — суфікс. Коренем дерева буде вершина, що відповідає мінімальному елементу масиву A, лівим піддеревом буде декартове дерево префікса, а правим піддеревом буде декартове дерево суфікса.

На наступному зображенні ви можете побачити один масив довжини 10 і відповідне йому декартове дерево.

Запит мінімуму на відрізку [l, r] еквівалентний запиту найнижчого спільного предка [l', r'], де l' — це вершина, що відповідає елементу A[l], а r' — вершина, що відповідає елементу A[r]. Справді, вершина, що відповідає найменшому елементу на відрізку, має бути предком усіх вершин на цьому відрізку, а отже, і l', і r'. Це автоматично випливає з властивості min-купи. А ще вона має бути найнижчим предком, бо інакше l' і r' були б обидва або в лівому, або в правому піддереві, що породжує суперечність, оскільки в такому разі мінімум навіть не лежав би на відрізку.

На наступному зображенні ви можете побачити запити LCA для запитів RMQ [1, 3] і [5, 9]. У першому запиті LCA вершин A[1] і A[3] — це вершина, що відповідає A[2], яка має значення 2, а в другому запиті LCA вершин A[5] і A[9] — це вершина, що відповідає A[8], яка має значення 3.

Таке дерево можна побудувати за час $O(N)$, а алгоритм Фараха-Колтона і Бендера може виконати попередню обробку дерева за $O(N)$ і знаходити LCA за $O(1)$.

Побудова декартового дерева

Ми будуватимемо декартове дерево, додаючи елементи один за одним. На кожному кроці ми підтримуємо коректне декартове дерево з усіх оброблених елементів. Легко бачити, що додавання елемента s[i] може змінити лише вершини на найправішому шляху — починаючи від кореня й щоразу переходячи до правого нащадка — у дереві. Піддерево вершини з найменшим, але більшим або рівним за s[i] значенням стає лівим піддеревом s[i], а дерево з коренем s[i] стане новим правим піддеревом вершини з найбільшим, але меншим за s[i] значенням.

Це можна реалізувати за допомогою стека, що зберігає індекси найправіших вершин.

C++

vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!s.empty() && A[s.top()] >= A[i]) {
        last = s.top();
        s.pop();
    }
    if (!s.empty())
        parent[i] = s.top();
    if (last >= 0)
        parent[last] = i;
    s.push(i);
}

Python

parent = [-1] * n
s = []  # стек індексів вершин найправішого шляху
for i in range(n):
    last = -1
    while s and A[s[-1]] >= A[i]:
        last = s.pop()
    if s:
        parent[i] = s[-1]
    if last >= 0:
        parent[last] = i
    s.append(i)

TypeScript

const parent: number[] = new Array(n).fill(-1);
const s: number[] = []; // стек індексів вершин найправішого шляху
for (let i = 0; i < n; i++) {
  let last = -1;
  while (s.length > 0 && A[s[s.length - 1]] >= A[i]) {
    last = s.pop()!;
  }
  if (s.length > 0)
    parent[i] = s[s.length - 1];
  if (last >= 0)
    parent[last] = i;
  s.push(i);
}

Go

parent := make([]int, n)
for i := range parent {
	parent[i] = -1
}
s := []int{} // стек індексів вершин найправішого шляху
for i := 0; i < n; i++ {
	last := -1
	for len(s) > 0 && A[s[len(s)-1]] >= A[i] {
		last = s[len(s)-1]
		s = s[:len(s)-1]
	}
	if len(s) > 0 {
		parent[i] = s[len(s)-1]
	}
	if last >= 0 {
		parent[last] = i
	}
	s = append(s, i)
}