Вступление
Пожалуй, большинство из вас встречалось с такой структурой данных (точее, расширением обычного Дерева Отрезков), как Segment Tree Beats. Как известно, эта структура помогает в решении множества задач (подробнее про это здесь: https://codeforces.com/blog/entry/57319). Но, тем не менее, этот набор идей ограничивается не только лишь Деревом Отрезков. Его также можно успешно использовать и с другими структурами, которые позволяют выполнять запросы на отрезках. Например, STB можно совместить с корневой декомпозицией или Декартовым Деревом.
...А главное, зачем?
На самом деле, это несёт больше теоретическое значение, чем практическое. Тем не менее:
1) Существуют запросы на отрезках, которые не решаются с помощью ДО. Использовать STB в таких случаях не представляется возможным, однако применить корневую декомпозицию или Декартово дерево можно.
2) Есть задачи, решение которых гораздо упрощается, если применять "Sqrt Beats". Иногда такой способ достигает большей эффективности, потому что такое решение требует в разы меньше памяти. Также, например, в большинстве случаев можно довольно легко добавить векторизацию (самописную или автовекторизацию, поставив O3 и avx2 в таргетах компиляции программы). Несомненно, векторизовать можно и само STB, сделав из него уже расширенное B-Tree, но это займет в разы больше строк кода и времени.
Sqrt Beats
Основная идея
Основные идеи практически не отличаются от идей STB. Вкратце их можно описать так: при запросе на отрезке будем обрабатывать блок декомпозиции "втупую", если не можем обработать его за быстро. Тогда в среднем это будет работать достаточно хорошо.
Задача 1.
Обычно, говоря про STB, приводят в пример классическую задачу $$$ \%= $$$ на отрезке, присвоение в точке и сумма на отрезке (https://codeforces.com/contest/438/problem/D). Рассмотрим её реализацию посредством корневой декомпозиции. Соответственно, для блока будем хранить максимум и минимум на нем, а также сумму.
Очевидно, самой тяжелой для нас будет являться операция $$$ \%= $$$. Давайте посмотрим, когда мы сможем обрабатывать блок за быстро.
1) $$$max < mod$$$ Тогда, очевидно, в блоке ничего не поменяется и его трогать не надо.
2) $$$min = max$$$ Это условие равносильно тому, что все числа на отрезке равны. Значит, после взятия по модулю $$$mod$$$ они останутся равными и станут $$$min \% mod$$$ соответственно, что равно $$$max \% mod$$$. Таким образом, сумма в блоке также пересчитается за $$$O(1)$$$.
Соответственно, если мы нигде не можем выиграть себе время, то просто пройдемся по блоку "втупую", сделав $$$\%=$$$ для каждого числа в нем и пересчитав сумму.
Итого код будет выглядеть примерно так:
Его можно также написать с помощью корневой по степеням двойки примерно следующим образом, что будет работать чуть быстрее:
Почему это работает?
Давайте оценим асимптотику:
1) get: $$$O(\frac{n}{k} + k)$$$
2) set: $$$O(k)$$$
3) mod:
Тут все не так однозначно, поэтому оценим амортизированно:
Введем потенциал $$$\Phi$$$ нашей структуры, который определим как
У операции $$$\%=$$$ есть одно полезное свойство: $$$a\ \text{mod}\ b < \frac{a}{2}$$$, если учесть что $$$b \le a$$$
Тогда верно следующее:
1) Каждая операция $$$=$$$ в точке увеличивает наш потенциал не более чем на $$$\log{C}$$$ и требует $$$O(k)$$$ времени.
2) Каждая операция $$$\%=$$$ занимает времени $$$O(\frac{n}{k}+k+x\cdot k)$$$ (где $$$x$$$ — количество "плохих" блоков запроса, которые мы не можем обработать за $$$O(1)$$$) и уменьшает потенциал хотя бы на $$$x$$$.
Тогда суммарное время работы этой операции будет $$$O(q\cdot\frac{n}{k} + qk + k\cdot\sum{x})$$$.
Но $$$\sum{x}\le \Phi_0+q\cdot\log{C} = (n + q)\cdot\log{C}$$$, так как потенциал всегда неотрицательный.
Значит, итоговая асимптотика работы алгоритма $$$O(q\cdot(k\log{C}+\frac{n}{k})+nk\log{C})$$$, что достигает примерного оптимума при $$$k \approx \sqrt{\frac{n}{\log{C}}}$$$ и становится $$$O((q+n)\sqrt{n\log{C}})$$$.
На деле же алгоритм работает гораздо быстрее из-за особенностей операции $$$\%=$$$. Например, в той же задаче, такое решение отрабатывает за ~300мс, что довольно быстро (тратит памяти такое решение около 1 МБ, что на порядок меньше, чем решения, использующие STB).
Задача 2.
На самом деле, нам никто не запрещает делать присвоение не в точке, а на отрезке. От этого код практически не поменяется. Опять же, оценим асимптотику работы:
1) get: $$$O(\frac{n}{k} + k)$$$
2) set: $$$O(\frac{n}{k} + k)$$$
3) mod:
Введем потенциалы блоков $$$\phi_i$$$, которые определим как
т.е. как сумму логарифмов значений по всем подотрезкам из равных значений, встречающихся в блоке декомпозиции, или 0, если все числа в блоке равны. Также введем потенциал $$$\Phi$$$ нашей структуры, который определим соответственно как $$$\Phi = \sum\phi_i$$$.
Тогда, соответственно, верно следующее:
1) Операция $$$=$$$ делает потенциалы блоков, которые захватывает полностью, равными 0 и увеличивает потенциал блока, который затрагивает частично, не более чем на $$$2\log{C}$$$. То есть $$$\Phi$$$ увеличивается не более чем на $$$4\log{C}$$$.
2) Операция $$$\%=$$$ работает за $$$O(\frac{n}{k}+k+x\cdot k)$$$, где $$$x$$$ — количество "плохих" блоков запроса, которые мы не можем обработать за $$$O(1)$$$. Обрабатывая каждый "плохой" блок мы уменьшаем $$$\Phi$$$ хотя бы на $$$1$$$, а, обрабатывая блок, который захватываем частично, увеличиваем потенциал не более чем на $$$2\log{C}$$$.
Значит, суммарное время работы этой операции будет (по аналогии с доказательством выше) $$$O(q\cdot\frac{n}{k} + qk + k\cdot\sum{x})$$$, что эквивалентно $$$O(q\cdot\frac{n}{k} + k(n + q)\cdot\log{C})$$$.
Значит, итоговая асимптотика работы не отличается от асимптотики предыдущей задачи и равна $$$O((q+n)\sqrt{n\log{C}})$$$.
Задача 3.
До этого мы рассматривали задачи, которые можно было написать, используя Segment Tree Beats. Теперь рассмотрим следующую задачу:
1) Мы можем делать операции изменения как и в Задаче 1 ($$$=$$$ в точке и $$$\%=$$$ на отрезке).
2) Запрос циклического сдвига влево на 1 на отрезке.
3) Есть запрос "посчитать количество чисел равных $$$k$$$ на отрезке ($$$k$$$ могут быть различные для запросов)".
Пример этой же задачи без первого типа запросов здесь. Соответственно, решать нашу новую задачу будем посредством совмещения оригинальной идеи и идеи из Задачи 1.
Идея оргинальной задачи — split + rebuild, то есть каждые $$$k$$$ запросов будем перестраивать нашу корневую. В каждом блоке декомпозиции, соответственно, поддерживаем unordered_map {число : кол-во вхождений}. А запрос циклического сдвига, соответственно, обрабатывается за $$$O(\frac{n}{k} + k)$$$ посредством перемещения элемента из одного блока в другой. Теперь добавим сюда все то, что мы уже делали раньше. Если $$$min = max$$$ то мы также можем пересчитать информацию в блоке за $$$O(1)$$$, значит весь принцип не поменялся. Заметим, что если мы введем такую же систему потенциалов как и в первой задаче, то запрос сдвига не будет изменять наш суммарный потенциал, значит, асимптотика работы не изменится.
Итого получаем такое же время работы, то есть $$$O((q+n)\sqrt{n\log{C}})$$$.
Упражнение: Напишите это.
Интересный факт.
Доказательство асимптотики работы этой структуры в разы легче, чем доказательство той же идеи в Segment Tree Beats и может быть хорошим упражнением, чтобы попрактиковаться в амортизационном анализе.
Treap Beats?
Итак, чем мы пользовались в оригинальном STB?
Мы имеем двоичное сбалансированное дерево (ДО), где в узлах хранится информация о подотрезке, за который они отвечают. Забавный факт: Декартово Дерево также удовлятворяет этим условиям. А, значит, идейно принцип вообще не будет ничем отличаться от STB.
Что это позволяет делать? Это позволяет совместить некоторые задачи, которые решаются ДД (например, меняют относительный порядок элементов или добавляют новые) и исходные идеи.
Например:
1) Операция реверса отрезка, $$$\%=$$$ на отрезке, $$$=$$$ на отрезке + запрос суммы на отрезке. (Также можно решать предыдущей техникой и split-rebuild).
2) Вставить элемент на позию $$$x$$$ в массив, min= на отрезке + запрос суммы и максимума на отрезке (Ji Driver Treap???).
3) Циклический сдвиг отрезка на $$$k$$$, деление нацело на отрезке, прибавление на отрезке + запрос суммы, максимума, минимума на отрезке.
4) Запрос поменять местами четные и нечетные элементы отрезка местами, min= на отрезке, прибавление на отрезке + запрос gcd на отрезке.
А также еще бесконечное множество возможных вариаций операций.
