Раздел «Образование».FIVTLecturesTerm3Lecture5:
<< Список лекций ФИВТ, 3-й семестр, 2009 г.

! Лекция 5. Задача RMQ. Дерево интервалов

Формулировка задачи

Дана последовательность чисел {a(0), a(1),a(2), ..., a(n-1)}.

Требуется быстро отвечать на большое количество запросов RMQ(i,j): Чему равно минимальное число в кусочке {a(i),a(i+1),..., a(j-1)}?

Есть возможность потратить некоторое время (время препроцессинга) на то, чтобы быстро отвечать на эти запросы.

Решение, основанное на динамическом программировании

Одна из идей динамического программирования - параметризация множества задач и кеширование ответов на задачи.

Задача 1. Найдите решение, которое создает таблицу с ответами на все возможные запросы RMQ(i,j) (это будет треугольная таблица размера O(n^2)) за время, пропорциональное размеру этой таблицы. Используйте тот факт, что ответ на RMQ(i,j) можно получить из ответов на RMQ(i, j-1), RMQ(i+1,j).

Задача 2. Можно во время препроцесинга вычислить заранее ответы на запросы вида RMQ(i, i + 2^k). Эти ответы помещаются в массив размера n * log n. Вычислите эту таблицу за время пропорциональное её размеру, используя тот факт, что ответ на RMQ(i, i+2^k) можно получить из ответов на RMQ(i, i+2^(k-1)), RMQ(i+2^(k-1), i+2^k).

Задача 3. Как, имея ответы на запросы вида RMQ(i, i + 2^k), получать ответы на запросы RMQ(i, j) для произвольных i и j за время O(1)?

Дерево интервалов

Дерево интервалов — это двоичное дерево, у которого листья равны заданным числам и обход листьев слева на право повторяет заданную последовательность. Каждая внутренняя вершина хранит число равное миниму из чисел её детей. Таким образом, в корне дерева интервалов находится минимальное из заданных чисел.

Дерево интервалов обычно хранят в массиве b размера 2*n. В конец массива помещают элементы массива a или ссылки на них.

for (i = n, j = 0; i < 2*n; i++, j++)
  b[i] = a[j];

Предполагается что у ячейки b[i] детьми являются ячейки b[2*i] и b[2*i + 1]:

for (i = n-1; i >= 1; i--)
  b[i] = min(b[2*i], b[2*i+1]);

Задача 4. Напишите функцию find_min(i,j, node), который в поддереве с корнем b[node] находит минимум RMQ(i,j). Предполагается, что полуинтервал [i,j) относится к поддереву с вершиной b[node]. Убедитесь, что время работы вашей функции есть O(log n).

Итоги

  preprocessing query
таблица n^2 n^2 1
таблица n * log n n * log n 1
дерево интервалов n log n
??? n 1