Лекция по корневой декомпозиции

Простейшая корневая на массиве

Задача 1

• += в точке
• сумма на отрезке

Разбиваем массив на корень кусочков. В каждом кусочке храним соответствующий массив-подотрезок и его сумму.

Задача 2

• Дополнительно += на отрезке.

Дополнительно храним модификатор в каждом блоке. Проталкиваем когда нужно (например когда нужно поработать с нецелым блоком)

Как обычно, если модификатор простой (например как выше), то можно вообще не проталкивать.

Корневая на массиве, блок cо структурой данных внутри

• += на отрезке
• количество чисел ≤ x на отрезке.

Решение: поддерживаем для каждого отрезка обычный и сортированный массив.

Split-Rebuild корневая

Задача:

• sum на отрезке
• del(index)
• insert(index, value)

Массив "физической памяти". Список "отрезков-указателей".

• split(pos): получить разрез в нужном месте
• rebuild(): получаем [0: n).

Остальные операции выражаем через split.

Например, чтобы вычислить sum(l, r), делаем split(l), split(r+1), после чего для каждого отрезочка внутри [l; r] считаем суммы на нём (например через префиксные суммы физической памяти).

Время работы:

• split: O(#число отрезков)
• rebuild: O(#число отрезков + #длина массива)
• sum: split + O(#число отрезков).
• insert: split + O(1)

Невыгодно иметь много отрезков. Каждые sqrt(n) операций делаем Rebuild ⇒ O(n sqrt(n)).

Вариации:

• Делаем split, когда стало слишком много кусочков

• Меняем Rebuild(): будем строить sqrt(n) кусочков длины sqrt(n).

  Позволяет, например, разрезать отрезок за его длину. Как и раньше делаем Rebuild раз в sqrt(n) операций.

• Поддерживаем инвариант, что каждый кусочек имеет длину от sqrt(n) до 2 sqrt(n).

  Сильно менее-приятная реализация, зато нет амортизации.

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

В предыдущих пунктах мы делили массив на корень кусочков длины корень. Это позволяло делать какие-то операции с массивом за корень. Давайте попробуем пойти в другую сторону и делить не массив, а запросы к нему.

Задача: Винни-Пух и бочки мёда

Дано n изначально пустых бочек мёда, в i-й из них помещается не более, чем b_i мёда.

Происходит q операций вида:

• На отрезке от l_i до r_i добавляем арифметическую прогрессию: К первому элементу добавляем "a", ко второму "a + b" и так далее.

Вывести для каждой бочки первый запрос, когда она заполнится.

Решение

Разгребаем запросы блоками по k=sqrt(q)

Если предположить, что никакой бочонок не переполняется, то не очень сложно c помощью сканлайна за O(k + n) найти итоговый объём каждого бочонка.

Если никакой бочонок не наполнился, то больше ничего не делаем.

Иначе для каждого бочонка, который только что заполнился (то есть который был не заполнен до блока из K запросов, но стал заполнен после) делаем следующее:

• Откатим состояние этого бочонка к началу блока из K запросов (например сохраним состояние массива в тот момент времени)
• Затем линейным циклом применим к этому бочонку K запросов блока и найдём первый, после которого бочонок заполнится.

Оценим время работы:

• Всего есть q/k блоков, каждый из которых мы применяем за время O(n + k), итого O(q/k (n + k)).
• А ещё каждый из бочонков не более одного раза поменяет своё состояние на заполненое, после чего мы просмотрим для этого бочонка весь блок запросов заново. Это O(n k).
• Итого O(q/k (n + k) + nk) ⇒ k = sqrt(q) и O(q + n sqrt(q)).

Задача о Винни-Пухе: параллельный бинпоиск

Отвлечёмся немного в сторону от темы SQRT: предыдущую задачу можно решить с помощью параллельного бинпоиска.

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

Есть лишь один нюанс: нельзя совсем просто взять и вычислить предикат бинпоиска ok(mid) быстро.

Давайте сделаем небольшой трюк и будем делать все n бинпоисков одновременно. Состояние бинпоиска для i-го бочонка характеризуется числами <l, r, mid>, где l и r это текущие границы бинпоиска, а mid это место, где нужно узнавать истинность предиката бинпоиска

Итак, у нас есть n бочонков, q запросов, и для каждого бочонка позиция, в которой нужно узнать истинность предиката

Давайте сделаем сканлайн с деревом отрезком сверху вниз: для каждого элемента в ДО храним сколько там есть мёда (в промежуточных вершинах можно даже ничего не хранить), делаем массовую операцию "добавить прогрессию на отрезке". Когда нас просят вычислить предикат бинпоиска, спрашиваем сколько мёда в этом бочонке и сдвигаем бинпоиск или в одну сторону, или в другую

Оценим время работы. Нужно сделать log(q) фаз бинпоиска. Каждая из фаз работает за сканлайн с деревом отрезков, то есть за (n + q)log(n).

Итоговое время работы составляет O((n + q) log(n) log(q)).

Задача про set

• add(x): добавить в сет новый элемент
• count(l..r): сколько элементов со значением в таком диапазоне

Решение

Храним большом сортированном массиве и буферизируем новопришедшие числа отдельно.

count делает бинарный поиск в большом массиве и пробегается по всему малому, O(log(n) + sqrt(n)).

add либо просто добавляет в малый массив, либо сливает два массива на O(n log n)).

Для фазы из k+1 запросов: add k раз работает время O(1) и один раз O(n log(n)).

При выборе k = sqrt(n log(n)) получаем решение за O(sqrt(n log(n))) на операцию.

Можно перестраивать большой массив за O(n), если отсортировать малый отдельно и сделать std::merge. В таком случае оптимально k = sqrt(n) и решение за O(n sqrt(n)).

Dynamic Connectivity Offline

Запросы:

• connect(v, u)
• disconnect(v, u)
• connected?(v, u)

Все запросы даны в offline.

Решение

Бьём запросы на блоки по корню.

Внутри блока не более корня рёбер меняют свой статус присутствия.

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

В графе не более n вершин и 2k рёбер, обращаем внимание, что dfs работает за O(k), а не за O(n).

k := sqrt(n) ⇒ время работы O(n sqrt(n)).

Чтобы сделать dfs за O(k) можно использовать "быстрое очищение" массива used. Это можно сделать одним из двух способов:

• Запоминать те вершины, что мы пометили как used в стек, а потом его откатить.
• Использовать метки текущего времени. Вершина помечена, если used[v] == cur_t, операция cur_t++ очищает used.

Корневая на графе

Задача на графе.

Дан граф из n вершин и m рёбер. Происходят запросы:

• color[vertex] := c
• найти количество различных цветов у соседей вершины v

Решение

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

Def. Скажем, что вершина жирная, если у неё степень больше sqrt(E).

Значит нужно как-то научится решать задачу для жирных вершин. sum_v deg(v) = 2E ⇒ жирных не более O(sqrt(E)).

Заранее насчитаем "базовый ответ" (с массивом/set) для всех жирных вершин.

Каждый раз, когда перекрашиваем вершину, пробегаем по всем её жирным соседям. Их не более корня, так как в принципе в графе их тоже не более корня (но нужно заранее сохранить жирный подсписок).

Корневая со строками

Задача про строки

Дан текст и некоторый набор строк-шаблонов.

Найти (например посчитать суммарное количество) всех совпадений. Текст ограничен как 10⁵, суммарная длина шаблонов такая же.

Решение:

Суммарная длина шаблонов 10⁵ ⇒ количество различных длин не более sqrt(2 * 10⁵).

Если бы все шаблоны были бы одной длины, то мы бы решили задачу хешами.
Если разных, то сгруппируем по длине и переберём длину.

Mо

Задача min на отрезке

Дан массив из n элементов, нужно ответить на q запросов "узнать минимум на [l; r]".

Все запросы даны в offline, то есть на них можно ответить одновременно.

Обычно мы применяем Мо, когда функция от отрезка сложнее, чем минимум, но для простоты иллюстрации обсудим именно минимум.

Решение:

Если знать (multi)-set значений, которые есть на отрезке, то ответ легко вычиcлить

Если насчитать set для одного отрезка, то его пересчитать для сдвинутого отрезка (l++, l--, r++ или r--), за O(log n) на одну позицию.

Если правильно определить отсортировать все отрезки, то получается O(n sqrt(n) log(n)).

Отрезки выгодно сортировать по <l/k, r>, где k = sqrt(n) (предполагаем, что n≈q).

Оценим время работы:

• Пусть t_сдвига = t_{запроса} = O(1), тогда:
• Если l/k = const, то r только растёт между запросами. Всего есть n/k бакетов, в каждом из которых правая граница движется только направо, не более чем на n.
• Если l/k = const, то l меняется не больше чем на k. Тем самым между соседними запросам в одном бакете переход по l за не более k (и таких запросов ≤ n).
• Теперь рассмотрим переходы между бакетами. Всего есть n/k бакетов и переход между запросами из двух бакетов происходит не более чем за n.
• Итого получили O(n^2 / k + nk) ⇒ оптимально k=sqrt(n) и итого O(n sqrt(n)).

Разгоняем МО!

Хотим сделать то же самое, что и выше, но быстрее, без лишнего логарифма, используя как внутреннюю структуру данных корневую.

Замечаем, что МО работает за O(n sqrt(n) * t_сдвига + n * t_{запроса}).

Выгодно перебалансировать в сторону второго.

Например заведём корневую: будем хранить в ячейке количество вхождений числа (пусть числа лежат от [0; n]), а также для каждого блока размера sqrt(n) храним суммарное число вхождений в нём

Тогда t_сдвига = O(1), а t_{запроса} = O(sqrt(n))

Итого целиком решение за O(n sqrt(n)).

Мо и обновления, трёхмерное Мо

Рассмотрим задачу на МО, но теперь разрешим запросы точечного обновления массива.

Тогда запрос чтения <l, r> можно описать как <t, l, r>, где t --- количество запросов модификации до этого чтения.

Раньше в МО состоянием являлся отрезок <l, r> и какая-то структура данных об этом отрезке.

Теперь скажем, что состояние это <t, l, r>, массив для текущего времени и структуру данных об этом отрезке в этот момент.

Раньше у нас было t_сдвига одной из границ отрезка на ±1. Заметим, что теперь мы можем двигать на ±1 ещё и время.

Отсортируем запросы лексикографически по <t/k, l/k, r>, где k = n^2/3 и обойдём в таком порядке.

Несложно доказать (аналогично с тем, как мы это сделали для обычного МО), что время работы будет O(n^5/3).

На самом деле алгоритм МО это алгоритм обхода точек на плоскости за O(n sqrt(n)). Только что мы его обобщили до 3d и получили O(n^5/3). Можно пойти дальше и обобщить до размерности k. Тогда получится асимптотика O(n^{2 - 1/k})