Структуры данных

Sparse Table: O(1) запросы на отрезках

Цели урока

  • Понять когда Sparse Table лучше Segment Tree
  • Освоить идею перекрывающихся степеней двойки
  • Реализовать построение таблицы
  • Отвечать на запросы за O(1)
  • Применить для LCA

Предварительные знания

  • Segment Tree
  • Segment Tree

У вас миллиард исторических котировок акций. Пользователь задаёт миллион запросов 'минимальная цена за период X-Y'. Segment Tree даст O(log n) на запрос. Sparse Table - O(1). При миллионе запросов это разница в 20 раз.

  • LCA в деревьях (выражения, DOM, генеалогия)
  • Range Minimum Query в статических массивах
  • Суффиксные массивы (LCP queries)
  • Исторические данные без изменений

Эквивалентность RMQ и LCA у Бендера и Фарах-Колтона

Сама sparse table относится к более старому фольклору, но её современную роль закрепили Майкл Бендер и Мартин Фарах-Колтон в статье 2000 года 'The LCA Problem Revisited'. Они ясно показали, как задача Lowest Common Ancestor на дереве сводится к Range Minimum Query на глубинах, записанных во время Euler tour, и обратно. Sparse table это естественный инструмент для статической части RMQ в этом сведении: она предвычисляет ответ для каждого интервала, длина которого является степенью двойки, за O(n log n), а затем отвечает на любой запрос за O(1), объединяя два перекрывающихся интервала-степени двойки. Это работает именно потому, что операции вроде минимума, максимума и gcd идемпотентны, и перекрытие не учитывает ни один элемент во вред результату. Чёткое разделение на шаг предобработки за O(n log n) и запросы за O(1) сделало sparse table стандартным строительным блоком для статических задач на отрезках.

Проблема: Быстрые запросы без обновлений

**Segment Tree** отвечает за O(log n), но что если данные **не меняются**?

СтруктураПредобработкаЗапросОбновление
Segment TreeO(n)O(log n)O(log n)
Sparse TableO(n log n)**O(1)**Нет

**Sparse Table** жертвует обновлениями ради **O(1) запросов**. Идеально для статических данных!

**Применения:**

  • Lowest Common Ancestor (LCA) в деревьях
  • Range Minimum Query (RMQ) на статических массивах
  • Суффиксные массивы и LCP
  • Биржевые данные - исторический min/max за период

Sparse Table лучше Segment Tree когда:

Идея: Перекрывающиеся степени двойки

**Ключевое наблюдение:** любой отрезок можно покрыть **двумя** отрезками длины степени 2.

**Перекрытие допустимо!** Для min/max/gcd повторный подсчёт элемента не меняет результат: min(a, a) = a.

Такие операции называются **идемпотентными**: повторное применение к тому же элементу не меняет результат.

**Сумма НЕ идемпотентна!** Перекрытие посчитает элементы дважды. Для суммы используй Segment Tree.

Какая операция НЕ подходит для Sparse Table?

Построение таблицы

**Sparse Table** - 2D массив: `st[i][j]` = результат операции на отрезке `[i, i + 2^j - 1]`.

**Сложность построения:** O(n log n) времени и O(n log n) памяти.

st[3][2] для массива содержит min на отрезке:

Запрос за O(1)

Для запроса `[l, r]` находим максимальную степень 2, которая помещается в отрезок.

**Почему O(1)?** Предвычисление log даёт O(1) вычисление степени. Два обращения к таблице - тоже O(1).

Сложность одного запроса в Sparse Table:

Применение: LCA за O(1)

**LCA (Lowest Common Ancestor)** - важная задача на деревьях. Sparse Table решает её за O(1)!

**Алгоритм (Euler Tour + RMQ):**

  1. Euler Tour: обход дерева с записью каждого узла при входе/выходе
  2. Для каждого узла запоминаем первое вхождение в tour
  3. LCA(u, v) = узел с минимальной глубиной между first[u] и first[v]
  4. Это задача RMQ → Sparse Table!

**Итог:** O(n) Euler Tour + O(n log n) Sparse Table = O(n log n) предобработка, O(1) LCA.

LCA через Sparse Table сводится к задаче:

Sparse Table

  • Для идемпотентных операций (min, max, gcd)
  • Предобработка: O(n log n), Запрос: O(1)
  • Не поддерживает обновления!
  • Два перекрывающихся отрезка покрывают любой интервал
  • Используется для LCA за O(1)

Range Query структуры

Каждая структура имеет свои компромиссы.

  • Segment Tree — O(log n) с обновлениями
  • Fenwick Tree — Сумма на префиксах

Связанные уроки

  • ds-19-segment-tree — Дерево отрезков тоже отвечает на запросы диапазона, но допускает обновления
  • ds-21-fenwick-tree — Дерево Фенвика даёт обновляемые суммы диапазона за O(log n)
  • alg-19-divide-conquer — Предвычисленные блоки степеней двойки берутся из разделяй и властвуй
  • alg-35-bit-manipulation — Декомпозиция запроса использует степени двойки и log-индексацию
  • ds-01-arrays — Таблица - это просто 2D массив предвычисленных ответов
  • alg-36-prefix-sum
Sparse Table: O(1) запросы на отрезках

0

1

Войти