Всем привет
Я хотел бы рассказать вам о структуре данных, которая, я считаю, заслуживает широкой известности в сообществе CP. Вы не найдете эти структуры данных в своей стандартной библиотеке, поэтому нам нужно будет реализовать их самостоятельно. Мы собираемся решить две очень полезные проблемы в CP с разреженной таблицей: проблема наименьшего общего предка (LCA) и проблема минимального запроса диапазона (RMQ).
Разреженная таблица – это структура данных, которая позволяет отвечать на запросы со статическим диапазоном. Он может ответить на большинство запросов диапазона за 0 (log N), но эффективно отвечает на запросы минимального диапазона (или эквивалентные запросы максимального диапазона) за 0 (1) времени. Он выполняет предварительную обработку заранее, чтобы на запросы можно было ответить эффективно.
Допустим, у вас есть массив «arr», и вы хотите выполнить несколько запросов. Каждый запрос должен вычислять функцию F над подмассивом [L, R]: F(arr[L], arr[L + 1], …, arr[R]). С разреженной таблицей вы можете выполнять каждый запрос за O (log (N)) (N - размер arr) с начальной предварительной обработкой O (N * log (N)). Он часто служит заменой дерева сегментов в случае неизменяемых данных.
Ограничения
Разреженная таблица может использоваться тогда и только тогда, когда:
- Массив является неизменяемым (т. е. запросы не изменяют его)
- Функция F ассоциативна: F(a, b, c) = F(F(a, b), c) = F(a, F(b, c)).
Понимание разреженной таблицы
Представьте, что вы смотрите фильм, и ваш друг уверяет вас, что между 00:10 и 01:01 (чч:мм) нет ничего интересного. Кроме того, он рассказывает вам историю из того периода. Теперь вам не нужно смотреть его целиком, и вы только что сэкономили свое драгоценное время. А теперь представьте себя в ситуации, когда вам очень хочется посмотреть фильм Человек-паук: Домой нет пути. Но из-за плотного графика вы не можете попасть в кинотеатр. Предположим, у вас есть много друзей, которые смотрели отдельные части фильма, а в совокупности — весь фильм. Теперь вам не обязательно идти в театр, при условии, что ваши друзья достаточно красноречивы. Вы просто спрашиваете их о фильме, и они рассказывают его вам по частям.
Подобно этому, разреженные таблицы помогают вам сэкономить много времени, они обычно хранят данные фрагментами и эффективно отвечают, когда это необходимо.
Идеология
Мы знаем, что любое число можно представить в двоичном виде как сумму различных степеней двойки.
E.g. 19=(10011)2=16+2+1.
С той же идеей любой интервал может быть однозначно представлен как объединение интервалов с длинами как различными степенями двойки.
E.g. [2,14]= [2,9] ∪ [10,13] ∪ [14,14],
Здесь полный интервал имеет длину 13, а отдельные интервалы имеют длины 8, 4 и 1 соответственно. И здесь объединение состоит не более чем из log2(R-L+1) множества интервалов.
Чтобы вычислить значение некоторого интервала длины 2 ^ k, нужно просто объединить два интервала размера 2 ^ (k − 1), поэтому каждый интервал можно вычислить за постоянное время.
Основная идея разреженных таблиц заключается в предварительном вычислении всех ответов на запросы диапазона со степенью длины два. После этого можно ответить на другой запрос диапазона, разбив диапазон на диапазоны со степенью двойки, просмотрев предварительно вычисленные ответы и объединив их для получения полного ответа.
Создание разреженной таблицы
Разреженную таблицу можно построить восходящим образом с помощью динамического программирования. Основная идея заключается в предварительном вычислении ответов всех подмассивов размером 2^j (где j варьируется от 0 до Log n). Мы будем использовать двумерный массив для хранения ответов на предварительно вычисленные запросы, таблица[i][j] будет хранить ответ для диапазона [i,i+(1‹‹j)−1] длины 2^j. Размер двумерного массива будет N×(K+1), где N — длина массива, а K = ceil(log2(N)).
Давайте рассмотрим пример запроса Range Sum, чтобы понять построение разреженной таблицы.
Приложения
Минимальные запросы диапазона (RMQ)
Это запросы, в которых разреженная таблица сияет. Запрос минимального диапазона решает задачу поиска минимального значения в диапазоне массива.
Алгоритм
При вычислении минимума диапазона не имеет значения, обрабатываем ли мы значение в диапазоне один или два раза. Поэтому вместо того, чтобы разбивать диапазон на несколько диапазонов, мы также можем разделить диапазон только на два перекрывающихся диапазона с длиной, равной степени двойки. Таким образом, мы можем эффективно ответить на RMQ с временной сложностью 0 (1).
Итак, мы можем вычислить минимум диапазона [L, R] с помощью:
Здесь на данном рисунке мы должны найти минимальный элемент в диапазоне [0,8] . Здесь длина диапазона равна log2(8–0+1)~3, поэтому новый диапазон будет разделен как min([0,8])=min( min([0,7]),min([5, 8])) ), который получается из предварительно вычисленной двумерной разреженной таблицы, равен min([0,8])=min(2,1)=1. Следовательно, минимум полного диапазона [0,8] равен 1, что также можно проверить вручную.
Реализация C++
Временная сложность
for RMQ: 0(1)
Младший общий предок
Пусть G — дерево. Для каждого запроса вида LCA(u, v) предполагается найти наименьшего общего предка узлов u и v, т.е. мы хотим найти узел w, лежащий на пути от u до корневого узла, который лежит на пути от v к корневому узлу, и если есть несколько узлов, мы выбираем тот, который находится дальше всего от корневого узла.
Алгоритм
Для каждого узла мы предварительно вычислим его предка над ним, его предка на два узла выше, его предка на четыре выше, его предка на восемь выше и т. д., и сохраним его.
Мы будем использовать 2D-массив, скажем, up, up[i][j] хранит 2^j-го предка узла, где i=1...N, j=0...ceil(log(N)).
Мы можем вычислить этот массив, используя методы обхода дерева, предпочтительно DFS.
Для каждого узла мы также будем помнить время, когда этот узел встречается в первый раз («во времени»), и время, когда мы его покинули (т.е. после того, как мы посетили все его узлы в поддереве и вышли из функции DFS). ("Время выхода"). Мы можем использовать эту информацию, чтобы определить, является ли узел предком другого узла в постоянное время.
- Узел u будет предком узла v тогда и только тогда, когда его время «входа» меньше или равно времени «входа» узла v, а время «выхода» узла u больше или равно времени «выхода». узла v.
Сначала мы проверяем, является ли узел из двух предком другого или нет, и если один узел является предком другого, то это LCA этих двух узлов, в противном случае мы находим узел, который не является общим предком как u, так и v и является самый высокий (то есть узел x такой, что x не является общим предком u и v, но является up[x][0]) в дереве. Найдя такой узел (пусть это будет x), мы выводим первого предка x, т.е. up[x][0], который и будет требуемым LCA.
* While building the sparse table we will use up[i][j]= up[up[i][j-1]][j-1];
Здесь, на данном рисунке, мы видим, что мы проверим узел 14 и узел 15. От узла 15 мы сначала совершим прыжок на 4 единицы и проверим, является ли узел 3 предком узла 14 или нет, да, это так. . Проверять будем в порядке убывания степени двойки. Затем мы сделаем небольшой скачок на 2 единицы и проверим, является ли узел 7 предком узла 14 или нет, нет. Затем из узла 7 мы совершим прыжок на несколько различных степеней двойки. Но каждый раз он будет приземляться на узел, который является предком узла 14. Тогда мы придем к выводу, что узел 7 является самым высоким узлом, который не является предком как узла 14, так и узла 15. И тогда мы придем к выводу, что 2⁰( =1)-й предок узла 7 является младшим общим предком узлов 14 и 15. Следовательно, узел 4 является LCA узлов 14 и 15 на приведенном выше рисунке.
Временная сложность
0(NlogN) for pre-processing 0(logN) for each query.
Реализация C++
Тренировочные задачи
Дополнительные ресурсы
Спасибо за чтение
Это мой первый блог, поделитесь своим мнением в комментариях ниже.
Обо мне
Меня зовут Адитья Бисвакарма, я студент 2-го курса бакалавриата по информационным технологиям в IIIT Аллахабаде, член подразделения Competitive Coding Wing, Гикхейвен, IIIT Аллахабад. Подключайтесь к Linkedin.
