Чтобы погрузиться в эту структуру данных, мы рассмотрим вопрос, который ляжет в основу статьи.
Проблема:
Вам предоставляется неизменяемый массив (массив, который не изменяется). И набор запросов. Каждый запрос содержит диапазон от l до r. Вам необходимо вычислить идемпотентную функцию f от l до r , т.е. найдите значение:
f (arr [l], arr [l + 1],… arr [r])
Идемпотентная функция - это функция, которая действительно меняет свое значение при многократном применении. Примеры таких функций: min, max, gcd, lcm и т. Д.
min (min (2,3,4)) совпадает с min (2,3,4).
Решение:
Для таких вопросов есть несколько вариантов решения. Вы можете использовать дерево сегментов для решения проблемы с предварительной обработкой N * log (N) и log (N) время запроса.
Но обратите внимание, что приведенный здесь массив является неизменным, т.е. в данном массиве нет обновлений. И данная функция идемпотентна. Благодаря этим двум условиям мы можем использовать другую мощную структуру данных, которая поможет нам решить этот вопрос при предварительной обработке N * log (N) и константе время запроса.
Интуиция:
Разреженная таблица - это не что иное, как особый тип таблицы dp. В этой структуре данных table [i] [j] хранит значение функции для диапазона [i, i + 2 ^ j) .
Почему степень двойки, а не любого другого числа? Что ж, все мы знаем, что любое число можно записать как сумму уникальных степеней 2. Таким образом, любой диапазон можно выразить однозначно и как сумму степеней 2, начиная с l.
Возьмем пример. Предположим, вам предоставлен диапазон от 3 до 16. Размер диапазона составляет 14. 14 можно записать как 8 + 4 + 2. Таким образом, мы можем разделить диапазон как [3,10] + [11,14] + [15,16]. И мы можем получить значения этих диапазонов прямо из таблицы как table [3] [3], table [11] [2] и table [15] [1]. Нам просто нужно их объединить. Следует отметить, что из 14 вычислений у нас осталось только 3 вычислений. Таким образом, в основном разреженная таблица может дать ваш результат в log (N) (мы увидим впереди, как уменьшить этот log (N) в константу для идемпотентных функций).
Создание таблицы:
Построение разреженного стола - очень простой прием. Вы инициализируете базу таблицы, которая является table [i] [0] с теми же значениями, а для других значений вы строите таблицу снизу вверх:
table [i] [j] = f (table [i] [j-1], table [i + 2 ^ (j-1)] [j-1]] »
Обычно длина интервала x, если он разделен на интервалы длины x / 2 и x / 2. Таким образом, от l до l + x -1 вычисляется уже рассчитанное значение l на l + x / 2 -1 и l + x / 2 на l + x-1.
Фактическая реализация выглядит следующим образом:
Стоимость построения таблицы составит N * log (N).
Отвечая на вопросы:
Как мы уже обсуждали, любой диапазон можно разделить на сумму уникальных степеней 2. Поскольку мы уже предварительно вычислили эти значения, мы можем легко объединить диапазоны, чтобы ответить на запрос.
Чтобы получить ответ, вы начинаете с наивысшей степени, равной 2, и продолжаете снижаться. Если эта степень двойки меньше текущего размера диапазона, мы можем взять этот поддиапазон полностью, изменив l на l + power из 2 и перейдите к следующей степени двойки. Делайте это, пока не дойдете до r.
Реализация будет примерно такой:
Здесь сложность запроса будет log (N).
Оптимизация до постоянного времени:
Мы видим, что для идемпотентных функций любой запрос можно записать как:
пусть x будет наивысшей степенью двойки, которая меньше или равна размеру диапазона.
f ( l , r) = f( f( l, l+x), f( r-x, r) )
Обратите внимание, что некоторые элементы диапазона будут перекрываться. Например, запрос от 3 до 16 будет разделен на 3 на 10 и от 9 до 16 . Но min (arr [3] .. arr [16]) будет таким же, как min (min (arr [3] .. arr [ 10]), мин (обр [9] .. обр [16])).
Таким образом, наш запрос сводится к следующему:
Мы можем использовать постоянное время запроса только для идемпотентных функций, таких как min, max, gcd и т. Д. Для других, таких как sum, нам нужно log (N) время для обработки запроса.
Заключение и конец:
- Разреженную таблицу можно использовать для ответа на запросы диапазона в постоянное время для идемпотентных функций и log (N) для других функций с помощью N * log (N) время предварительной обработки.
- Разреженная таблица не поддерживает обновления. Для обновлений нам нужно перестроить всю таблицу, и рекомендуется переключиться на другие структуры данных, такие как дерево сегментов.
- Разреженная таблица намного быстрее, чем деревья сегментов.
Эту проблему рекомендую решать на практике с использованием разреженных таблиц. В редакционной статье метод разреженных таблиц не упоминается должным образом.
Вот ссылка на мою работу. Проверяйте, только если вы застряли.
Ссылка:
- Https://cp-algorithms.com/data_structures/sparse-table.html (В конце страницы есть очень хороший список проблем для этой темы).
