Минимум на отрезке и разреженная таблица

Если ты умеешь строить разреженную таблицу, знаешь, почему перекрытие годится для минимума и не годится для суммы, и понимаешь сведение LCA к RMQ через эйлеров обход, листай до «Теперь сам».

Как думаешь, зачем перекрывать отрезки

Мы уже умеем считать суммы на отрезках деревом отрезков за O(log n) на запрос. Прежде чем читать дальше, подумай: если массив НЕ меняется, можно ли отвечать быстрее - за константу? И что для этого достаточно предподсчитать, если разрешено накрывать запрос перекрывающимися кусками?

На что это похоже

Линейка с делениями разной длины. Чтобы измерить произвольный отрезок, необязательно иметь мерку точно его длины: хватит двух мерок, которые накрывают его с перехлёстом. Для вопроса «какой самый короткий предмет лежит на этом участке» перехлёст не мешает - предмет, посчитанный дважды, ответ не испортит. А вот для вопроса «сколько всего весят предметы» перехлёст всё испортит: часть посчитается дважды.

Механизм: таблица степеней двойки

LOG = n.bit_length()
st = [[0] * n for _ in range(LOG)]
st[0] = a[:]                                    # отрезки длины 1

for k in range(1, LOG):
    half = 1 << (k - 1)
    for i in range(n - (1 << k) + 1):
        st[k][i] = min(st[k-1][i], st[k-1][i + half])   # два куска по 2^(k−1)

def query(l, r):                                # минимум на [l, r], включительно
    k = (r - l + 1).bit_length() - 1            # наибольшее k с 2^k <= длины
    return min(st[k][l], st[k][r - (1 << k) + 1])

Запрос накрывается двумя отрезками длиной 2^k: один от левого конца, другой - упирающийся в правый. Вместе они покрывают весь запрос и, как правило, ПЕРЕСЕКАЮТСЯ в середине.

запрос [l .. r], длина 13, берём k = 3 (отрезки по 8):

l ─────────────── r
[■■■■■■■■]              ← st[3][l]      накрывает первые 8
     [■■■■■■■■]         ← st[3][r−7]    накрывает последние 8
     ^^^ перекрытие в 8 + 8 − 13 = 3 элемента - для минимума безразлично

Предподсчёт - O(n·log n) времени и памяти, запрос - O(1). Сравни с деревом отрезков из раздела про деревья: там запрос O(log n), зато массив можно МЕНЯТЬ. Разреженная таблица - для неизменяемых данных, и это её единственное, но принципиальное ограничение.

Сведение LCA к RMQ. Эйлеров обход дерева (не путать с эйлеровым путём в графе, который проходит каждое ребро ровно один раз, - здесь просто устоявшееся название) выписывает вершину при входе и ещё раз после возврата из каждого ребёнка:

обход дерева:  r → p → a → p → b → p → r → c → r
массив вершин:  r  p  a  p  b  p  r  c  r
массив глубин:  0  1  2  1  2  1  0  1  0
first[v] - позиция первого вхождения вершины v

euler, depths, first = [], [], [-1] * V

def walk(v, p, d):
    first[v] = len(euler)          # первое вхождение
    euler.append(v); depths.append(d)
    for u in adj[v]:
        if u != p:
            walk(u, v, d + 1)
            euler.append(v)        # вернулись - выписываем вершину ещё раз
            depths.append(d)

walk(root, root, 0)
# LCA(u, v): взять l, r = first[u], first[v] (упорядочив их) и найти позицию
# минимума в depths[l..r] - стоящая там вершина euler[поз] и есть ответ

Длина массива - ровно 2V − 1. Утверждение: LCA(u, v) - это вершина с НАИМЕНЬШЕЙ глубиной на отрезке между first[u] и first[v]. Значит LCA - это RMQ по массиву глубин, и после предподсчёта запрос стоит O(1).

Правило

Разреженная таблица: st[k][i] - минимум на отрезке длиной 2^k из позиции i; строится за O(n·log n) как минимум двух половин, запрос - минимум двух перекрывающихся отрезков за O(1). Перекрытие допустимо только для ассоциативных и ИДЕМПОТЕНТНЫХ операций (f(x, x) = x): минимум, максимум, НОД, побитовые И и ИЛИ; для суммы - нельзя. Массив должен быть неизменяемым; для меняющегося берут дерево отрезков (O(log n) на запрос). LCA сводится к RMQ эйлеровым обходом: наименьший общий предок - вершина минимальной глубины между первыми вхождениями u и v в массиве длины 2V − 1.

Разбор: строим таблицу и отвечаем на запрос

Массив a = [5, 2, 8, 1, 9, 3], n = 6.

st[0] = [5, 2, 8, 1, 9, 3]                       отрезки длины 1
st[1][i] = min(a[i], a[i+1]):  [2, 2, 1, 1, 3]   отрезки длины 2
st[2][i] = min(st[1][i], st[1][i+2]):  [1, 1, 1] отрезки длины 4

Запрос: минимум на [1, 4] (элементы 2, 8, 1, 9). Длина 4, значит k = 2. Берём min(st[2][1], st[2][4 − 4 + 1]) = min(st[2][1], st[2][1]) = 1. Здесь оба отрезка совпали - длина запроса оказалась точной степенью двойки.

Запрос [0, 4] (пять элементов). Длина 5, наибольшая степень двойки внутри - 4, значит k = 2. Берём min(st[2][0], st[2][4 − 4 + 1]) = min(st[2][0], st[2][1]) = min(1, 1) = 1. Первый отрезок накрыл позиции 0-3, второй - позиции 1-4; позиции 1, 2, 3 посчитаны ДВАЖДЫ, и ответ от этого не изменился. В этом вся суть приёма.

Теперь представь, что вместо минимума мы бы считали СУММУ. Сумма на [0,4] равна 5+2+8+1+9 = 25, а «сумма двух отрезков» дала бы (5+2+8+1) + (2+8+1+9) = 16 + 20 = 36 - перекрытие посчиталось дважды. Для сумм разреженная таблица не годится; там берут префиксные суммы (для статического массива) или дерево отрезков (для меняющегося).

Разбор: почему LCA - это минимум глубины

Возьмём эйлеров обход из блока выше: массив вершин r p a p b p r c r, глубины 0 1 2 1 2 1 0 1 0. Найдём LCA(a, b). Первое вхождение a - позиция 2, первое вхождение b - позиция 4. Смотрим отрезок позиций 2..4: глубины 2, 1, 2, минимум - единица на позиции 3, и там стоит вершина p. Ответ: LCA(a, b) = p ✓.

Почему так получается в общем случае. Между первыми вхождениями u и v обход обязан выйти из поддерева одной вершины и войти в поддерево другой, а сделать это можно только через их общего предка - обход дерева не умеет перепрыгивать. Значит LCA(u, v) на этом отрезке точно встретится. С другой стороны, все вершины на отрезке лежат в поддереве LCA (обход не поднимается выше, пока не закончит поддерево), а значит их глубина не меньше глубины LCA. Минимум глубины достигается ровно на нём.

Дальше остаётся техника: массив глубин статичен, запросов много - это RMQ, и разреженная таблица отвечает за O(1). Существует и более тонкое решение с предподсчётом O(n) и запросом O(1) (алгоритм Фарака-Колтона и Бендера), использующее то, что соседние глубины различаются ровно на единицу, - но на практике почти всегда хватает разреженной таблицы или двоичных подъёмов.

Что ломается без этого

Первое: применять разреженную таблицу к сумме - перекрытие посчитается дважды. Признак, по которому проверяют операцию: она должна быть ассоциативной (иначе не склеить половины при построении) И идемпотентной, f(x, x) == x (иначе нельзя перекрывать). У минимума, максимума и НОД так; у суммы и произведения - нет. Второе: строить её на меняющемся массиве - одно изменение требует перестроения O(n log n), здесь нужно дерево отрезков. Третье: ошибиться в формуле k - брать bit_length() без вычитания единицы, и тогда отрезок вылезет за границы запроса. Четвёртое: в сведении LCA к RMQ взять массив ВЕРШИН вместо массива ГЛУБИН и искать минимум по номерам вершин - номера произвольны и ответа не дают. Пятое: использовать first[v] как «любое вхождение» - подойдёт любое, но границы надо упорядочить: если first[u] > first[v], концы отрезка меняют местами.

Зачем это в работе

Разреженная таблица - стандартный инструмент для статических данных: минимумы и максимумы на отрезках логов, временных рядов, отсортированных массивов; запросы НОД на отрезке; поиск наибольшего общего префикса в суффиксных массивахРазбирается в разделе 17, глава «Суффиксный массив, LCP и суффиксное дерево»: Суффиксный массив: отсортировать все места, откуда можно читать (там LCP-запросыРазбирается в разделе 17, глава «Суффиксный массив, LCP и суффиксное дерево»: LCP: сколько общего у соседей по суффиксному массиву сводятся ровно к RMQ). Выбор между тремя инструментами этой главы стоит держать в голове как таблицу: двоичные подъёмы - O(V log V) памяти, O(log V) на запрос, легко расширяются (максимум на пути, k-й предок); разреженная таблица по эйлерову обходу - O(1) на запрос, но только LCA и только для статического дерева; дерево отрезков - если дерево или массив МЕНЯЮТСЯ. Есть и четвёртый путь - оффлайновый алгоритм Тарьяна, который отвечает на все запросы за один обход с помощью непересекающихся множеств из прошлого раздела; он требует знать все запросы заранее, зато почти линеен. Выбирают по тому же принципу, что и всегда: сколько запросов, меняются ли данные, известны ли запросы заранее.

Теперь сам

Массив a = [4, 7, 2, 9, 3, 6, 1, 8]. Построй st[1] и st[2] и ответь на запрос минимума на отрезке [2, 6].