Корневая декомпозиция

По данным реанализа, летом 2025 года в Алматы 53 дня были со средней температурой от +25°, а летом 1951-го — ни одного. Это ответы на вопрос «сколько дней периода были не холоднее x» по архиву погоды за 85 лет — 31 046 дней. Пока архив не меняется, на такой вопрос легко ответить и в лоб. Но в архив приходят поправки: «датчик с такого-то по такое-то число врал на полградуса». Тогда нужна структура, которая отвечает и на вопросы, и на поправки, причём сразу для целых периодов. Дерево отрезков здесь спотыкается: «сколько значений не меньше x» не складывается из ответов двух половин. Блоки по √n справляются.

Синие полосы на нижнем графике — целые блоки: у каждого есть отсортированная копия его дней, и на вопрос он отвечает одним двоичным поиском. Красные — два разрезанных блока на краях периода: их дни приходится смотреть по одному. Переключите размер блока. При B = 16 разрезанные края дёшевы, но целых блоков сотни. При B = 4096 целых блоков почти нет, зато края — тысячи дней. Посередине, около √n, обе части малы.

Идея

Корневая декомпозиция режет массив на блоки по B элементов и хранит для каждого блока сводку — то, что позволяет ответить за весь блок сразу: сумму, отсортированную копию, общую добавку. Отрезок [l, r] накрывает несколько блоков целиком и разрезает не больше двух. Целые блоки отвечают по сводкам, разрезанные — поэлементно. Изменение целого блока записывается в его сводку, изменение части блока — в элементы, после чего сводку пересчитывают.

Сводки не обязаны склеиваться — в этом сила приёма. Дереву отрезков нужно, чтобы ответ на отрезок собирался из ответов половин. Блокам достаточно, чтобы каждый блок отвечал сам за себя, а ответы блоков складывались в итог: число тёплых дней — это сумма чисел тёплых дней по блокам.

Почему корень

Запрос стоит не больше 2B элементов в разрезанных блоках плюс n/B целых блоков. Первое слагаемое растёт с B, второе падает.

Если целый блок отвечает не за один шаг, а двоичным поиском за log₂ B, лучший размер немного сдвигается вверх, к √(n log n), но на практике берут круглое число рядом с √n, и разница — проценты. Листинг ниже проверяет это на всём архиве: 800 вопросов и поправок, размеры блоков от 16 до 4096.

Три корня

Корень можно брать не только от длины массива. Приём один — разделить работу на «большие» и «маленькие» части так, чтобы тех и других было не больше √n, — а применять его можно по-разному.

• По позициям. Блоки массива, как выше. Подходит, когда сводку блока легко пересчитать и легко спросить.
• По времени. Структура перестраивается заново раз в √q операций, а изменения между перестройками копятся в буфере и при каждом запросе учитываются по одному. Запрос стоит «по перестроенной структуре плюс не больше √q правок», и перестройки делятся на √q операций. Так можно добавить изменения в структуру, которая умеет только отвечать.
• По значениям. Ключи делят на частые, которых встречается больше √n раз, и редкие. Частых не больше √n, и для каждого можно хранить всё заранее; у редкого не больше √n вхождений, и их можно перебрать. Так считают, например, пары и треугольники в графах, где у одних вершин миллионы соседей, а у других единицы.

Порядок Мо

Ещё один корень — в порядке, в котором отвечать на запросы, если все они известны заранее. Возьмём «Войну и мир» и спросим про 500 случайных отрывков из первых 60 000 слов: сколько в каждом разных слов? Удобно держать окно [left, right] со счётчиком каждого слова и числом слов, встреченных хотя бы раз. Расширить окно на слово — увеличить счётчик; сузить — уменьшить. От отрывка к отрывку края окна сдвигаются, и цена ответа — число шагов краёв.

Если отвечать в порядке вопросов, окно мечется по всему тексту и делает 15,8 миллиона шагов — больше, чем если считать каждый отрывок заново (9,8 миллиона). Сортировка по левому краю помогает наполовину: левый край идёт ровно, зато правый скачет. Порядок Мо режет ось левых краёв на блоки и внутри блока сортирует по правому краю.

Возвраты правого края в начале каждого блока — пустая работа, и их убирает змейка: в чётных блоках правый край идёт по возрастанию, в нечётных — по убыванию, и окно не возвращается. На отрывках «Войны и мира» блоки получаются по 2683 слова, порядок Мо делает 1,65 миллиона шагов, змейка — 1,13 миллиона: в 8,7 раза меньше, чем подсчёт каждого отрывка заново.

Код

Первый листинг строит блоки на всём архиве погоды и проводит через них один и тот же поток из 640 вопросов и 160 поправок — с блоками разного размера. Ответы сверяются с решением в лоб. Печатается, сколько клеток просмотрено поодиночке и сколько целых блоков ответили двоичным поиском — в среднем на операцию.

31046 days, 640 queries and 160 corrections; a whole pass is 31046 cells
  block   cells per op  blocks per op
     16             21            647
     64             88            161
    176            242             58
   1024           1369              9
   4096           5022              2

Блок 176 — это √31 046. Если считать двоичный поиск в блоке за log₂ B шагов, получается около 680 шагов на операцию при 176, около 1050 при 64 и около 1460 при 1024 — минимум рядом с корнем. Средний период в потоке — около десяти тысяч дней, так что в лоб операция стоила бы в пятнадцать раз дороже.

Второй листинг — алгоритм Мо. Шаги окна для каждого порядка он считает без самого окна, как сумму скачков краёв, а затем по-настоящему проходит отрывки змейкой со счётчиками слов и сверяет ответы с подсчётом в лоб.

War and Peace, the first 60000 words, 13436 distinct; 500 passages
order of the passages        steps of the window
each passage from scratch                9787759
as asked                                15843335
by the left end                          6348731
Mo, blocks of 2683                       1648509
Mo, the snake                            1128367
the longest passage: 57148 words, 12952 of them distinct

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

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

Где работает

• Колоночные базы и форматы файлов. В Parquet у каждой группы строк хранятся минимум и максимум столбца, в ClickHouse данные лежат гранулами по 8192 строки с отметками индекса. Запрос «где температура больше 25» пропускает группы, чей максимум меньше, не читая их, — те же сводки блоков, только размер блока подобран под диск, а не под √n.
• Олимпиадные задачи на отрезках. Число различных значений, самое частое значение, «сколько не меньше x» с правками — всё, где ответ половин не складывается. Алгоритм Мо — стандартный инструмент для офлайн-запросов.
• Перестройка по расписанию. Структуру, которая умеет только отвечать, делают изменяемой, перестраивая её раз в √q операций и учитывая свежие правки поштучно.

История

Разбить массив на блоки размера √n — приём настолько простой, что у него нет автора: он встречается в задачах и учебниках с тех пор, как стали считать операции. У порядка запросов имя есть. Его называют по Мо Тао, который с товарищами применил и распространил приём в 2009 году в задаче о вероятности вытянуть из отрезка два одинаковых носка. Тот же порядок раньше описали Кент, Ландау и Зив-Укельсон в 2005 году, в работе о сборке генов из экзонов, — и, вероятно, не они первые.

Задачи

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