Разреженная таблица

85 лет погоды Алматы — 31 046 дней — нужно нарисовать линией шириной в экран. На экране сотни столбцов пикселей, и на каждый приходятся десятки дней. Если в столбце нарисовать один день из десятков, график соврёт: морозный день, попавший между выбранными, просто исчезнет. Честный график для каждого столбца показывает весь размах его дней, от минимума до максимума. Найти минимум и максимум каждого столбца при каждом сдвиге и масштабе — это заново пройти по всем дням окна. Разреженная таблица отвечает на каждый такой вопрос двумя чтениями, сколько бы дней ни было в столбце.

При 700 столбцах кадр — 1400 вопросов к таблице и 2800 чтений, в любом масштабе: и когда в столбце 44 дня, и когда в нём один. Простой проход по окну во всю ширину прочитал бы 31 046 дней. Теперь двигайте ползунок масштаба и тяните график вбок. Внизу — столбец под указателем, день за днём: синий блок начинается от его левого края, оранжевый кончается у правого, оба длиной в одну и ту же степень двойки, и посередине они перекрываются. Ответ — меньший из двух минимумов, и перекрытие ему не мешает.

Идея

Заранее посчитаем минимум каждого отрезка, длина которого — степень двойки: строка k таблицы хранит минимум отрезка [i, i + 2^k) для каждого i. Строка k склеивается из двух половин строки k − 1, поэтому вся таблица строится за O(n log n). Любой отрезок длины L накрывают два блока длины 2^k, где 2^k — наибольшая степень двойки, не превосходящая L: один от левого края, другой до правого. Минимум отрезка — меньший из минимумов этих двух блоков.

Это предподсчёт того же рода, что префиксные суммы, только хранится не «от начала до i», а «от i на 2^k вперёд». Поэтому и запросы устроены иначе: префиксные суммы вычитают, а таблица склеивает два ответа. Таблица «разреженная», потому что хранит ответы не для всех отрезков, а только для тех, чья длина — степень двойки. Для 31 046 дней таблица всех отрезков заняла бы 481 942 581 клетку, а разреженная — 432 938: в тысячу с лишним раз меньше, и ответ всё равно за два чтения. Номер строки для отрезка длины L — это ⌊log₂ L⌋, номер старшей единицы L: в Python L.bit_length() - 1, в Go bits.Len(uint(L)) - 1, в процессоре — одна инструкция подсчёта ведущих нулей (о ней — в статье о битовых трюках).

Почему перекрытие не мешает минимуму

Идемпотентны минимум и максимум, наибольший общий делитель, побитовые И и ИЛИ. Сумма — нет: x + x ≠ x, и общие элементы двух блоков войдут в ответ дважды. В листинге ниже осадки за 2023 год, сложенные по двум блокам по 256 дней, дают 706,2 мм вместо настоящих 562,5: 147 дней посчитаны дважды. Попробуйте сами — на шестнадцати июльских днях, где таблица видна целиком.

Каждая клетка строки k стоит под первым днём своего блока; нажмите на неё — подсветятся две клетки строки ниже, из которых она собрана. Сейчас выбраны дни 3–14: двенадцать дней, блоки по восемь, перекрытие в четыре. Для максимума всё сходится — самый жаркий день, 31 градус 14 июля, лежит в оранжевом блоке. Переключите на сумму, и перекрытие посчитается дважды. Сумма температур, кстати, — настоящая мера: агрономы складывают среднесуточные температуры выше 10 градусов за сезон и называют это суммой активных температур. Считать её нужно префиксными суммами, а не этой таблицей.

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

Сколько это места

Строк ⌊log₂ n⌋ + 1, в строке k — n − 2^k + 1 клеток. Для 31 046 дней это 15 строк и 432 938 клеток на одну таблицу — в 14 раз больше самих данных. Для минимума и максимума нужны две таблицы. На миллионе элементов строк уже 20, и таблица целых чисел по восемь байт займёт полторы сотни мегабайт. Поэтому разреженная таблица хороша, когда данные не меняются и вопросов очень много; когда памяти жалко, есть дерево отрезков с O(log n) на запрос в O(n) памяти. А есть и схемы с линейной подготовкой и ответом за O(1): таблица строится не над элементами, а над минимумами блоков по log n элементов, а внутри блоков ответы находят другим способом — так устроен алгоритм Фишера и Хойна 2006 года.

Изменить один элемент дёшево не выйдет: он входит в блоки всех строк, всего до n клеток. Поэтому таблица — структура для неизменных данных. Дописывать элементы в конец, впрочем, можно: новый элемент добавляет по одной клетке в каждую строку, и каждая считается из двух уже готовых, O(log n) на элемент. Так таблица годится для журнала, который только растёт, — например, для ряда погоды, к которому раз в сутки добавляется новый день.

Почему блоки именно степеней двойки, а не, скажем, троек? Любая длина L лежит между 2^k и 2^k+1, поэтому двух блоков по 2^k всегда хватает, чтобы накрыть отрезок, и они никогда не вылезают за его края. Со степенями тройки понадобилось бы до трёх блоков, а строк стало бы меньше в log₂ 3 ≈ 1,6 раза — выигрыш в памяти, проигрыш в каждом запросе. Двоичная таблица вдобавок находит номер строки одной инструкцией процессора.

Код

Таблица минимумов и максимумов над всеми днями и три графика в 700 столбцов: весь ряд, 2010-е и 2023 год. Каждый столбец программа проверяет честным проходом — ответы таблицы совпадают. В конце — ловушка суммы.

1941-01-01..2025-12-31: 31046 days in 700 columns, 2800 table reads (a plain pass reads 31046 days); the coldest column 2017-12-26..2018-02-08, -25.5
2010-01-01..2019-12-31: 3652 days in 700 columns, 2800 table reads (a plain pass reads 3652 days); the coldest column 2018-01-26..2018-01-30, -25.5

Обратите внимание на строки листинга про 2010-е и 2023 год: когда дней в окне немного больше, чем столбцов, или даже меньше, проход по ним ничуть не дороже таблицы. Таблица выигрывает, когда точек в окне на порядки больше, чем пикселей: сотни лет по дням, год по секундам, — и когда кадров много, как при перетаскивании графика. Агрегацию «минимум, максимум, первая и последняя точка на столбец пикселей» в 2014 году описали Уве Югель и соавторы под названием M4: этих четырёх точек достаточно, чтобы линейный график из сотен тысяч точек нарисовался попиксельно так же, как из всех. Там столбцы считаются запросом к базе за один проход по данным; таблица делает то же без прохода.

Сколько это стоит

Замер — только запросы, без построения: случайные отрезки неизменного массива, минимум. Просмотр отрезка, дерево отрезков снизу вверх и таблица.

Таблица отвечает за постоянное время: на Python 0,12–0,18 мкс от тысячи до четверти миллиона элементов — это в основном цена самого интерпретатора, на Go 2–10 нс, и рост на Go — промахи кэша, а не работа. Дерево отрезков медленнее в 6–15 раз на Python и в 11–30 раз на Go, просмотр — в тысячи раз на больших массивах. Платой за это служит построение и память: в замере таблица для четверти миллиона элементов — 18 строк, около 4,2 миллиона клеток.

Общий предок как минимум на отрезке

Главное применение таблицы — не графики, а деревья. Обойдём дерево в глубину и будем записывать вершину каждый раз, когда в неё входим или в неё возвращаемся: получится обход Эйлера длиной 2n − 1. Между первым появлением вершины u и первым появлением вершины v обход побывает в их наименьшем общем предке и не поднимется выше него — значит, общий предок — это самая неглубокая вершина на этом отрезке обхода. Вопрос о дереве превратился в минимум на отрезке массива глубин, и разреженная таблица отвечает на него за O(1).

Так в 2000 году Майкл Бендер и Мартин Фарах-Колтон в статье «Задача LCA ещё раз» показали, что оптимальный поиск общего предка устроен просто. Первыми ответ за O(1) после линейной подготовки получили Дов Харел и Роберт Тарьян в 1984 году, но их алгоритм, как написано в статье Бендера и Фарах-Колтона, был слишком сложен, чтобы реализовать его на деле; Барух Шибер и Узи Вишкин в 1988 году его упростили, но не до конца. Бендер и Фарах-Колтон перенесли на обычную машину параллельный алгоритм Беркмана, Бреслауэра, Галила, Шибера и Вишкина, и первая ступенька в нём — та самая таблица, которую они назвали Sparse Table. Подробнее об общих предках — в статье о наименьшем общем предке; вторая задача ниже — общий предок в дереве файлов этого сайта.

Ещё одно место, где таблица работает как деталь большего механизма, — наброски HyperLogLog: набросок объединения глав — поэлементный максимум регистров, и в задаче про главы «Войны и мира» максимум на отрезке глав берётся из разреженной таблицы. В суффиксном массиве длина общего префикса двух суффиксов — минимум на отрезке массива общих префиксов соседей, тоже запрос к таблице.

Задачи

В первой нужно отвечать на сотни тысяч вопросов «когда было жарче всего» по настоящей погоде, и подвох в одинаковых температурах: нужен самый ранний из жарких дней, а это тоже можно уложить в таблицу. Во второй — найти ближайшую общую папку двух файлов в дереве этого сайта через обход Эйлера.