Разреженная таблица (sparse table): минимум на отрезке за O(1)

Коротко

Разреженная таблица отвечает на запрос минимума или максимума на отрезке за константное время — быстрее дерева отрезков. Плата: массив должен быть неизменяемым.

Идея

Предподсчитаем ответы для всех отрезков, длина которых является степенью двойки.

table[k][i] — минимум на отрезке длины 2^k, начинающемся с позиции i.

массив:  [3, 1, 4, 1, 5, 9, 2, 6]

k=0 (длина 1):  3  1  4  1  5  9  2  6
k=1 (длина 2):  1  1  1  1  5  2  2
k=2 (длина 4):  1  1  1  1  2
k=3 (длина 8):  1

Каждая строка строится из предыдущей: отрезок длины 2^k — это два отрезка длины 2^(k-1).

table[k][i] = min(table[k-1][i], table[k-1][i + 2^(k-1)])

Хитрость запроса: перекрытие

Произвольный отрезок [l, r] не обязан иметь длину-степень двойки. Но его можно покрыть двумя перекрывающимися отрезками нужной длины.

отрезок [2, 6], длина 5
берём k = 2 (длина 4):

[2, 3, 4, 5]
      [3, 4, 5, 6]
       ↑ перекрытие

Перекрытие не мешает — минимум от минимумов остаётся минимумом, даже если часть элементов учтена дважды.

Именно это свойство называется идемпотентностью: min(x, x) = x. Оно есть у минимума, максимума, НОД и битовых И/ИЛИ, но нет у суммы — там перекрытие удвоит общую часть.

Реализация

import math


class SparseTable:
    def __init__(self, arr: list[int], func=min):
        self.func = func
        n = len(arr)
        self.log = [0] * (n + 1)

        # предподсчёт логарифмов, чтобы не считать их в запросе
        for i in range(2, n + 1):
            self.log[i] = self.log[i // 2] + 1

        levels = self.log[n] + 1
        self.table = [[0] * n for _ in range(levels)]
        self.table[0] = arr[:]

        for k in range(1, levels):
            length = 1 << k
            for i in range(n - length + 1):
                self.table[k][i] = func(
                    self.table[k - 1][i],
                    self.table[k - 1][i + (1 << (k - 1))]
                )

    def query(self, left: int, right: int):
        """Минимум на отрезке [left, right] включительно."""
        k = self.log[right - left + 1]
        return self.func(
            self.table[k][left],
            self.table[k][right - (1 << k) + 1]
        )


arr = [3, 1, 4, 1, 5, 9, 2, 6]
st = SparseTable(arr)

print(st.query(0, 3))   # 1
print(st.query(4, 7))   # 2
print(st.query(2, 6))   # 1

st_max = SparseTable(arr, max)
print(st_max.query(1, 5))   # 9

Предподсчёт логарифмов — важная деталь. Вызов math.log2 внутри запроса работает с плавающей точкой и может дать ошибку округления на границах. Целочисленная таблица и точнее, и быстрее.

Когда использовать

Правило простое: массив не меняется и нужен минимум или максимум — sparse table. Есть обновления или нужна сумма — дерево отрезков.

Если запросов мало, предподсчёт может не окупиться: O(n log n) на построение против O(n log n) на n запросов к дереву. Выигрыш появляется при большом числе запросов.

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

Классическая связка. Наименьший общий предок сводится к минимуму на отрезке эйлерова обхода дерева.

Строим эйлеров обход, для каждой позиции запоминаем глубину, и LCA двух вершин — это вершина минимальной глубины между их первыми вхождениями. Sparse table отвечает за O(1).

Итог: предподсчёт O(n log n), каждый запрос LCA — константа. Это быстрее двоичных подъёмов, которые дают O(log n) на запрос.

Другие применения

Минимум и максимум на отрезке в задачах на статические массивы.

НОД на отрезке — операция идемпотентна, подходит.

Битовые И и ИЛИ на отрезке.

Задачи с двумя указателями, где нужно быстро узнавать экстремум текущего окна без пересчёта.

Что делать, если нужна сумма

Сумма не идемпотентна, поэтому перекрытие сломает ответ. Варианты:

• префиксные суммы — O(1) на запрос, но нет обновлений;
• дерево Фенвика — O(log n) на запрос и обновление;
• disjoint sparse table — модификация, которая работает с любой ассоциативной операцией за O(1), но устроена сложнее.

Частые ошибки

Применение к сумме. Самая частая. Ответ будет завышен на величину перекрытия, и на маленьких тестах ошибка может не проявиться.

Вычисление логарифма через math.log2 в запросе. Ошибки округления дают неверный k на границах степеней двойки.

Выход за границы при построении. Цикл должен идти до n - length + 1, иначе обращение к несуществующим элементам.

Попытка обновить элемент. Придётся перестраивать всю таблицу за O(n log n).

Что запомнить

• Sparse table предподсчитывает ответы для всех отрезков длины-степени двойки.
• Запрос покрывается двумя перекрывающимися отрезками — отсюда O(1).
• Работает только с идемпотентными операциями: min, max, НОД, битовые И/ИЛИ.
• Для суммы и для обновлений нужно дерево отрезков или дерево Фенвика.
• Логарифмы предподсчитывайте целочисленно, а не через math.log2.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→