Информатика · объяснение и практика
Таблица минимумов: почему перекрытие блоков допустимо не всегда
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.
Саму таблицу блоков можно использовать и для некоторых других запросов, но способ объединения и стоимость запроса будут иными. Нельзя переносить обещание двух обращений к таблице на любую ассоциативную операцию. Перед выбором структуры проверьте, неизменяемы ли данные и допускает ли ваша операция повторный учёт перекрывающихся элементов.
От чтения к действию
А теперь — вы
Частые вопросы
Почему два перекрывающихся блока подходят для минимума?
Повторное включение одного и того же значения не меняет минимум: операция идемпотентна.
Можно по тем же двум блокам просто сложить суммы?
Нет. Перекрытие будет учтено дважды; нужен другой способ разложения либо другая структура.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Дерево Фенвика: обновления и префиксные суммы по битам индекса
Дерево Фенвика для суммы:lowbit,префикс из нескольких блоков и обновление одного элемента без перестройки всех префиксов.
Открыть темуЧисло путей в DAG: складываем способы, а не длины
Количество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.
Открыть тему