Информатика · объяснение и практика

Таблица минимумов: почему перекрытие блоков допустимо не всегда

Sparse Table для минимума на отрезке: блоки длины степени двойки, безопасное перекрытие и отличие от запроса суммы.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

В маршруте Графы, разрезы и динамические запросы · 10 тем

Главная мысль

Sparse Table заранее хранит ответы для блоков длины 1,2,4,8 и так далее. Минимум произвольного непустого отрезка можно получить из двух подходящих блоков, покрывающих его края. Их перекрытие не мешает минимуму, но тот же приём нельзя напрямую применять к сумме.

Предвычисляем ответы для готовых блоков

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

Предвычисление обычной таблицы требует порядка nlogn времени и памяти для массива длины n. Она предназначена для неизменяющегося массива. При изменении исходного элемента сохранённые ответы, которые его содержат, устаревают; нельзя продолжать использовать прежнюю таблицу как будто ничего не произошло.

Покрываем запрос двумя краями

Пусть индексы начинаются с нуля, а запрос включает обе границы L и R. Выбираем наибольшую степень двойки p,не превосходящую длину R−L+1. Берём блок от L длины p и блок, заканчивающийся в R,той же длины. Вместе они покрывают весь отрезок и могут перекрываться.

Для массива[11,9,8,4,7,6,2,10,5,3]найдём минимум с индекса 2 по 8. Длина 7,поэтому p=4. Первый блок с индексами 2…5 содержит 8,4,7,6 и даёт минимум 4. Второй,5…8,содержит 6,2,10,5 и даёт минимум 2. Ответ всего отрезка равен 2.

Пример

Запрос[2,8]покрывают блоки[2,5]и[5,8]. Их минимумы 4 и 2 дают общий минимум 2.

Элемент с индексом 5 входит в оба блока, но повторное рассмотрение числа 6 не меняет минимум. Удвоения вклада в результате не возникает.

Почему сумма требует другого обращения с блоками

Для минимума повтор одного значения безвреден: min(x,x)=x. Это свойство называют идемпотентностью. У суммы 1+1 не равно 1,поэтому перекрывшийся участок будет посчитан дважды. В нашем запросе сумма первого блока 25,второго 23; их сложение 48 не равно настоящей сумме 42.

Саму таблицу блоков можно использовать и для некоторых других запросов, но способ объединения и стоимость запроса будут иными. Нельзя переносить обещание двух обращений к таблице на любую ассоциативную операцию. Перед выбором структуры проверьте, неизменяемы ли данные и допускает ли ваша операция повторный учёт перекрывающихся элементов.

От чтения к действию

А теперь — вы

Два блока запроса перекрываются на элементах с суммой 6. Сложение их сумм дало 30. Чему равна сумма объединённого отрезка?

Частые вопросы

Почему два перекрывающихся блока подходят для минимума?

Повторное включение одного и того же значения не меняет минимум: операция идемпотентна.

Можно по тем же двум блокам просто сложить суммы?

Нет. Перекрытие будет учтено дважды; нужен другой способ разложения либо другая структура.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться