Я очень много слышу о данной теме, но не смог найти какие-то ресурсы на русском или английском языке и решил сделать перевод статьи ko_osaga. Данный перевод может содержать много неточностей, а также в нем не доступны ссылки, который есть в оригинальной статье.

В этой статье представлено новое дерево отрезков, называемое Kinetic Segment Tree. Элемент считается Kinetic, если он перемещается со временем, то есть, если элемент представляет собой линейную или многочленную функцию. Деревья отрезков часто встречаются на соревнованиях, как и Kinetic элементы (например, трик с выпуклой оболочкой), поэтому изучение их комбинации также может быть полезным. Также стоит отметить, что Kinetic свойства можно выявить даже в задачах, не связанных напрямую с Kinetic элементами (например, использование CHT в оптимизации DP), и рассмотреть, как Kinetic Segment Tree может быть применен.

Об этой структуре данных уже упоминалось в статьях на Codeforces, но недавно я нашел время для более тщательного изучения. На момент написания Kinetic Segment Tree, возможно, является малоизвестной структурой данных. Если вы интересуетесь новыми структурами данных, рекомендую прочитать.

Часто задачи на классические структуры данных сложны для решения, и обычно проще учиться на уже готовых материалах. Однако, если вы правильно поймете решение, это даст вам возможность изучить множество концептов. Цель этой статьи — глубокое понимание Segment Tree Beats и обучение на Kinetic Segment Tree, а также понимание преимуществ и недостатков структур данных и какие задачи они могут решать.

1. Segment Tree Beats

Segment Tree Beats — это техника, позволяющая решать запросы на отрезки, которые не могут быть решены обычной ленивой пропагацией. Это разновидность ленивой пропагации. Одна из задач, HDU 5306 Gorgeous Sequence, которую я слышал от иностранца, оказалась не решаемой обычной ленивой пропагацией, что показалось мне интересным. Эту задачу мы долго обсуждали на подготовке к IOI 2016, и она оказалась сложной даже с описанием на китайском.

Через шесть лет эта задача на Baekjoon Online Judge была решена более чем 200 людьми, и теперь есть много хороших материалов, объясняющих Segment Tree Beats. Я сам начал изучать это в 2020 году. Хотя есть и другие хорошие статьи, часто мне кажется, что стоит повторить, чтобы лучше понять доказательства.

Например, если нужно обновить только один отрезок, код может выглядеть так:

void update(int s, int e, int ps = 1, int pe = n, int p = 1, int v) {
    if (e < ps || pe < s)
        return;
    if (s <= ps && pe <= e) {
        tree[p].maxv = min(tree[p].maxv, v);
        return;
    }
    lazydown(p);
    int pm = (ps + pe) / 2;
    update(s, e, ps, pm, 2 * p, v);
    update(s, e, pm + 1, pe, 2 * p + 1, v);
    pull(p);
}

Такой код позволяет управлять максимальными значениями на отрезке при условии $$$A[i]=min(A[i], v)$$$. Однако, если требуется узнать сумму значений на отрезке после обновления, это становится сложнее. Один из способов решения — отказаться от обновления отрезка, если длина отрезка равна 1, тогда можно отслеживать изменения в сумме. Пример такого кода:

void update(int s, int e, int ps = 1, int pe = n, int p = 1, int v) {
    if (e < ps || pe < s)
        return;
    if (ps == pe) {
        if (tree[p].maxv > v) {
            tree[p].sum -= (tree[p].maxv &mdash; v);
            tree[p].maxv = v;
        }
        return;
    }
    /* ... */
}

Этот код поддерживает 3 типа запросов, но он медленный. Сложность функции update — $$$O(n)$$$, потому что все запросы на отрезки превращаются в запросы на точки. Однако, если условия обновления сильные, как $$$s \leq ps \land pe \leq e$$$, алгоритм завершится быстро, но с ограниченными возможностями операций. Если условия обновления слабые, как $$$ps == pe$$$, алгоритм будет медленным, но с высокой свободой операций. Segment Tree Beats находит оптимальное средство, сохраняя алгоритмическую сложность и увеличивая свободу операций. Это достигается за счет использования смарт техник, например:

void update(int s, int e, int ps = 1, int pe = n, int p = 1, int v) {
    if (e < ps || pe < s)
        return;
    if (s <= ps && pe <= e) {
        if (tree[p].maxv <= v) {
            // Не обновлять
            return;
        }
        // tree[p].maxv > v
        if (tree[p].smax < v) {
            tree[p].sum -= (tree[p].maxv - v) * tree[p].maxCnt;
            tree[p].maxv = v;
            return;
        }
        // tree[p].smax >= v, tree[p].maxv >= v не завершать
    }
    /* ... */
}

smax (второе по величине значение) — это максимальное значение среди элементов, которые меньше, чем максимальное

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

Простое доказательство. Пусть $$$f([s,e])$$$ — это количество различных значений в отрезке $$$[s, e]$$$. Сумма всех $$$f([s,e])$$$ для всех отрезков в дереве отрезков изначально равна $$$T(n) = T(n/2) + O(n)$$$, так что $$$O(n \log n)$$$. Если мы рассмотрим процесс обновления:

• Для узлов, которые полностью удовлетворяют $$$s \leq ps \land pe \leq e$$$:
• Узлы, удовлетворяющие условиям $$$tree[p].maxv \leq v || tree[p].smax < v$$$, не изменяют $$$f([s,e])$$$ и это же относится к их поддеревьям.
• Узлы, удовлетворяющие условиям $$$tree[p].maxv \geq v $$$ && $$$ tree[p].smax \geq v$$$, уменьшают $$$f([s,e])$$$ хотя бы на один, потому что $$$maxv \neq smax$$$, но оба становятся равными $$$v$$$.

• Узлы, которые не удовлетворяют условиям $$$e < ps || pe < s$$$, не рассматриваются.

• Для узлов, которые не удовлетворяют ни одному из условий, в их поддеревья может появиться новое значение $$$v$$$, так что $$$f([s,e])$$$ может увеличиться максимум на один.

Так как узлов, которые не удовлетворяют ни одному из условий, есть $$$O(\log n)$$$ на каждый запрос, то сумма всех $$$f([s,e])$$$ в процессе инициализации и обновления увеличивается на $$$O((n+q) \log n)$$$. Обновление запроса затрагивает $$$O(\log n)$$$ узлов, а также все узлы, удовлетворяющие условиям $$$tree[p].smax \geq v $$$ && $$$ tree[p].maxv \geq v$$$. При каждом посещении таких узлов $$$f([s,e])$$$ уменьшается хотя бы на один, так что общее количество посещений таких узлов через все запросы ограничено $$$O((n+q) \log n)$$$.

Сложное доказательство. Представим максимальное значение как тег. Узел получает тег в следующих случаях:

• Этот узел является корнем.
• Максимальное значение этого узла и его родительского узла различаются.

Тег, прикрепленный к узлу, будет максимальным значением его поддерева. При сохранении максимальных значений в узлах дерева отрезков узлы с одинаковыми максимальными значениями объединяются в одну связную компоненту, и значение сохраняется только в корне этой компоненты. Второе по величине значение любого узла является максимальным значением в строгом поддереве (поддереве без узла). Пусть $$$f([s,e])$$$ будет суммой количества тегов в поддереве узла $$$[s,e]$$$. Изначально это значение равно $$$O(n \log n)$$$.

Теперь давайте наблюдать за обновлением. При обновлении отрезка, как правило, каждому обновленному узлу будет присвоен один тег. Так как количество узлов равно $$$O(\log n)$$$ и глубина каждого также $$$O(\log n)$$$ (количество тегов, увеличивающихся, равно количеству предков нового тега), здесь увеличивается потенциал на $$$O(\log^2 n)$$$. Теперь рассмотрим случай, когда второе по величине значение больше или равно текущему обновленному значению (так что нужно рекурсивно спускаться дальше). В этом случае тег, предоставляющий это второе по величине значение, очевидно, исчезнет. Так что с каждым рекурсивным спуском потенциал уменьшается. Таким образом, сумма $$$f([s,e])$$$ увеличивается на $$$O((n+q \log n) \log n)$$$, и каждый запрос, спускающийся наивно, уменьшает это значение на 1 и более. Так что временная сложность становится $$$O((n+q \log n) \log n)$$$.

Несколько моментов для обдумывания:

Это доказательство можно немного изменить, чтобы доказать $$$O((n+q) \log n)$$$ — подробности см. в статье A simple introduction to "Segment tree beats". Здесь мы объяснили с добавлением $$$O(\log n)$$$, но это доказательство на самом деле является улучшением простого доказательства. Более простой способ понять это — не думать о $$$f([s,e])$$$, а просто о количестве тегов. Чтобы удалить один тег, нужно $$$O(\log n)$$$ времени. Изначально тегов $$$n$$$, и каждый запрос добавляет $$$O(\log n)$$$. Так что всего добавляется $$$O(n + q \log n)$$$ раз. Процесс наивного удаления тегов, если было удалено $$$k$$$ тегов, займет максимум $$$k \log n$$$ времени. Так что $$$O((n+q \log n) \log n)$$$.

Это доказательство можно использовать даже если запросы становятся более сложными, например:

$$$A[i]=min(A[i],Y)$$$ $$$A[i]=A[i]+X$$$

Операция $$$A[i] = A[i] + X$$$ также очевидно добавляет $$$O(\log n)$$$ тегов, потому что мы не используем различные числа, а используем понятие тега, что позволяет адаптировать доказательство для большего разнообразия операций. Кстати, $$$f([s,e])$$$ часто называют потенциальной функцией (potential function), которая часто встречается в анализе сложных алгоритмов. Одним из самых простых примеров использования потенциальной функции, кажется, является Segment Tree Beats.

2. Kinetic Segment Tree (Kinetic Tournament)

Этот раздел основан на следующей статье. Kinetic Segment Tree (KST) — это новая структура данных, которая изначально устанавливается в начальное время $$$t=0$$$ и поддерживает следующие запросы:

update(i, a, b): присваивает $$$(A[i], B[i]) = (a, b)$$$. query(s, e) $$$min_{i \in [s, e]} (A[i] \times t + B[i])$$$. heaten(T): устанавливает время как $$$t = T$$$, если $$$t \leq T$$$.

В широком смысле, Kinetic Segment Tree достаточно гибок. Например, управляемые функции не обязательно должны быть линейными, достаточно, чтобы их отношение менялось не более чем $$$O(1)$$$ раз в зависимости от $$$t$$$. Понятие heaten также не обязательно глобально, его можно рассматривать в контексте только отдельных отрезков. В этой статье мы будем рассматривать упомянутое выше определение, а обобщение можно рассмотреть в упражнениях.

Если рассматривать только упомянутый выше узкий KST, этот алгоритм может заменить некоторые известные структуры данных в определенных случаях. Например, если все запросы монотонно возрастают, K

ST можно рассматривать как дерево Li-Chao, поддерживающее запросы на отрезки. Сравнение функций:

Технически, Kinetic Segment Tree похож на Segment Tree Beats. Как и другие деревья отрезков, в листовых узлах сохраняются функции $$$A[i]x+B[i]$$$, а в нелистовых узлах — функции, минимизирующие $$$A[i]t+B[i]$$$ среди узлов поддерева. При фиксированном $$$t$$$ это легко сравнить, и запросы на отрезки и обновления не составляют проблем. Таким образом, функции update и query Kinetic Segment Tree работают за $$$O(\log n)$$$.

Теперь рассмотрим функцию heaten, которая корректирует внутреннюю информацию структуры данных, когда $$$t$$$ увеличивается. Если некоторый нелистовой узел сравнивает две функции своего поддерева, и наступает момент, когда их отношение меняется при $$$t$$$ больше текущего времени $$$t$$$, определим это время как $$$insec(v,t)$$$. Пусть $$$melt[v]$$$ будет минимальным из всех $$$insec(v,t)$$$ в поддереве $$$v$$$. В этом случае, если $$$melt[v]$$$ меньше или равно текущему времени, мы должны пересчитать приоритеты всех таких узлов, начиная с корня и двигаясь вверх.

Вот и все, что нужно знать об этом алгоритме. Не сложно понять, что он всегда найдет правильный ответ, но давайте проанализируем временную сложность алгоритма.

Теорема 1. Предположим, что нет обновлений. Тогда функция heaten Kinetic Segment Tree требует в сумме $$$O(n \log^2 n)$$$ операций. Докажем это. Рассмотрим любой отрезок $$$[s,e]$$$. Создадим Lower envelope только из прямых, находящихся в этом отрезке. Максимальное количество прямых, формирующих Lower envelope, равно $$$e - s + 1$$$, а количество изменений минимальной прямой не превышает $$$e - s$$$. Для узла $$$v = [l, r]$$$ определим $$$f(v)$$$ как количество оставшихся изменений минимальной прямой в отрезке $$$[l, r]$$$ и $$$\Phi(v)$$$ как сумму $$$f(v)$$$ по всему поддереву $$$v$$$. Если длина отрезка равна $$$n$$$, то $$$f(v) = O(n)$$$, а $$$\Phi(v) = O(n \log n)$$$. Таким образом, суммарный размер $$$\Phi(v)$$$ в начальный момент равен $$$O(n \log^2 n)$$$. Каждый раз, когда функция heaten посещает узел $$$v$$$, одна из точек пересечения в поддереве $$$v$$$ исчезает, так что $$$\Phi(v)$$$ уменьшается на 1. Таким образом, количество посещений, которое требуется функции heaten, не превышает суммы $$$\Phi(v)$$$, что равно $$$O(n \log^2 n)$$$.

Remark. Этот анализ использует потенциальную функцию в достаточно жестком смысле. Вот более простое объяснение. Размер Lower envelope каждого узла равен $$$O(n)$$$, так что общее количество точек пересечения, с которыми мы имеем дело, составляет $$$O(n \log n)$$$. Каждая точка пересечения требует посещения всех узлов на пути к корню, так что обработка каждой точки занимает $$$O(\log n)$$$. Умножив это, получим $$$O(n \log^2 n)$$$.

Теорема 2. Если есть обновления, функция heaten Kinetic Segment Tree требует в сумме $$$O(n \log^2 n \alpha(n))$$$ операций, где $$$\alpha(n)$$$ — это обратная функция Аккермана. Докажем это. Если смотреть по временной шкале, каждое обновление превращает объекты, которыми управляет KST, из прямых в отрезки. Можно считать, что каждое обновление уничтожает текущую прямую, создавая новую точку на правом конце и новую прямую на левом конце. Таким образом, когда мы создаем Lower envelope из $$$n$$$ отрезков, максимальное количество изменений минимального отрезка, которое может произойти, ограничено $$$O(n \alpha(n))$$$, и на самом деле существует конструкция, которая изменяется $$$\Omega(n \alpha(n))$$$ раз. Подробности можно найти в статье Davenport–Schinzel Sequences and Their Geometric Application. Таким образом, используя доказательство Теоремы 1, мы получаем указанный результат.

Теорема 3. Если объекты, управляемые Kinetic Segment Tree, не являются линейными функциями, а два различных объекта могут пересекаться максимум $$$s$$$ раз, функция heaten требует в сумме $$$O(\lambda_{s + 2}(n) \log^2 n)$$$ операций, где $$$\lambda_s(n)$$$ — это $$$n$$$-ый член последовательности Davenport–Schinzel порядка $$$s$$$. Теорема 3.1. Если функция обновления Kinetic Segment Tree поддерживает только операции вставки или только операции удаления, функция heaten требует в сумме $$$O(\lambda_{s + 1}(n) \log^2 n)$$$ операций. Здесь "пустая функция" означает $$$f(x) = \infty$$$. Теорема 3.2. Если функция обновления Kinetic Segment Tree не вызывается, функция heaten требует в сумме $$$O(\lambda_s(n) \log^2 n)$$$ операций.

Remark. Значения последовательности Davenport-Schinzel для малых $$$s$$$ следующие (Wikipedia):

$$$\lambda_0(n) = 1$$$ $$$\lambda_1(n) = n$$$ $$$\lambda_2(n) = 2n-1$$$ $$$\lambda_3(n) = 2n\alpha(n) + O(n)$$$ $$$\lambda_4(n) = O(n2^{\alpha(n)})$$$ $$$\lambda_5(n) = O(n2^{\alpha(n)}\alpha(n))$$$

Таким образом, если $$$s = O(1)$$$, последовательность Davenport-Schinzel фактически равна $$$O(n)$$$. Точные расчеты не приведены, но если предположить, что $$$\alpha(n) \leq 4$$$, то $$$\lambda_s(n)$$$ будет около $$$2^s n$$$. Те

оремы 1, 2, 3 показывают, что для того, чтобы достичь худшего случая, в каждом узле дерева отрезков должно быть много точек пересечения, и функция heaten должна перечислять их все. На самом деле, построение такого контрпримера для KST неочевидно, поскольку функция $$$\alpha(n)$$$ не так велика, так что, независимо от наличия запросов на обновление, можно считать, что сложность составляет примерно $$$O(\log^2 n)$$$.

3. Реализация и решение задач с помощью KST

3.1. Решение задачи с использованием Convex Hull Trick

BOJ 12795. Задача "Захват земли полуплоскостью" используется в качестве примера. Задача заключается в том, чтобы при вставке отрезка вида $$$ax+b$$$ быстро вычислять максимум $$$ax+b$$$ для данного запроса $$$x$$$. Обычный Convex Hull Trick не может решить эту задачу, и обычно используются четыре метода:

Использование дерева Li-Chao: $$$O(Q \log Q)$$$.

Управление верхней оболочкой отрезков с помощью Set (LineContainer): $$$O(Q \log Q)$$$.

Использование техники Bentley-Saxe для инкрементального изменения Convex Hull Trick: $$$O(Q \log^2 Q)$$$.

Оффлайн обработка запросов, после чего обычный Convex Hull Trick управляется с помощью дерева отрезков: $$$O(Q \log^2 Q)$$$.

Эту задачу можно решить с помощью Kinetic Segment Tree оффлайн за $$$O(Q \log^2 Q)$$$. Все отрезки вводятся изначально, после чего строится Kinetic Segment Tree для отрезков. Каждый запрос спрашивает максимум $$$ax+b$$$ для префикса отрезков. Запросы сортируются по возрастанию $$$x$$$ и обрабатываются в этом порядке, что позволяет использовать Kinetic Segment Tree.

Код решения BOJ 12795 с использованием Kinetic Segment Tree, написанный мной. (включая ненаписанный код update) Реализация не так сложна. Другие задачи, которые можно решить с помощью Kinetic Segment Tree:

Facebook Hacker Cup 2020 Round 2 Problem D: Log Drivin' Hirin'

Yosupo Judge: Line Add Get Min

BOJ. Начало паломничества

Первые две задачи из примеров, на самом деле, проще и быстрее решаются обычными структурами CHT. Это означает, что единственная задача, где оптимально использовать управление отрезками KST, это последняя задача, что может показаться немного скучным. Давайте рассмотрим другие задачи, которые можно решить с помощью KST.

3.2. Операция heaten на отрезках

Теперь мы объясним операцию, которая поддерживает heaten на запросах к отрезкам. Конкретно, мы сконструируем структуру данных, которая поддерживает следующие запросы для двух массивов одинаковой длины $$$[a_1, \ldots, a_n], [b_1, \ldots, b_n]$$$:

Максимум на отрезке: $$$max_{i \in [s, e]} b_i$$$

Heaten на отрезке: $$$b_i := b_i + t \times a_i$$$ для $$$i \in [s, e], t > 0$$$.

Использование принципов KST для поддержки этой операции несложно. Основной принцип заключается в том, что если порядок элементов нарушается, мы просто наивно решаем задачу. Максимум на отрезке обрабатывается точно так же, как и раньше. В случае операции Heaten на отрезке мы исследуем все соответствующие отрезки, для которых $$$melt[v] \leq t$$$, и меняем их порядок; если $$$melt[v] > t$$$, этот отрезок обрабатывается с помощью Lazy propagation. Если наивное решение из-за операции heaten не увеличивается слишком сильно, то временная сложность в конечном итоге не будет сильно отличаться от обычного KST. На самом деле разница не так велика, и вот почему.

Теорема 4. Если использовать Kinetic Segment Tree для обработки вышеуказанных запросов, задача может быть решена за $$$O((n + q \log n) \log^2 n)$$$. Докажем это. Предположим, что операция Heaten применяется только ко всему массиву. Для каждого листового узла представим его область как множество узлов, где значение $$$b_i$$$ этого листа максимально. Область листа $$$x$$$ включает $$$x$$$ и путь к его родителю. Когда происходит операция Heaten, одно из двух поддеревьев может измениться так, что лист $$$y$$$ получит лучшее значение, чем лист $$$x$$$. В этом случае $$$x$$$ потеряет свою область. Это происходит потому, что $$$a_x < a_y, b_x < b_y$$$, так что лист $$$x$$$ никогда не вернет эту область: значение листа $$$y$$$ всегда будет больше. Таким образом:

• Изначальный размер области равен $$$O(n)$$$.

• Каждый лист может получить максимум $$$O(\log n)$$$ области.

• Операция Heaten неизбежно уменьшает область листа, и этот процесс необратим, каждая такая операция занимает $$$O(\log n)$$$ времени.

• Все листья в сумме могут потерять максимум $$$O(n \log n)$$$ области. Операции потери занимают $$$O(\log n)$$$ времени, так что задача решается за $$$O(n \log^2 n)$$$.

Теперь предположим, что операция Heaten применяется только к отрезку. Для узлов, полностью содержащихся в отрезке, операция по-прежнему не влияет на порядок. Для поддеревьев, которые вообще не перекрываются с отрезком, ничего не происходит. Так что только для $$$O(\log n)$$$ узлов, частично перекрывающихся с отрезком, могут произойти изменения. Даже если область этих узлов уменьшалась, текущее обновление позволяет им подняться к корню. Таким образом, $$$O(\log n)$$$ листьев получают $$$O(\log n)$$$ областей, так что лист может в сумме получить максимум $$$O((n + q \log n) \log n)$$$ области. По этой логике задача решается за $$$O((n + q \log n) \log^2 n)$$$.

Кстати, Теорема 4 включает в себя Теорему 1. Отношения между "простым доказательством" и "сложным доказательством" в Segment Tree Beats аналогичны: это одно и то же доказательство, но этот вариант немного сложнее и доказывает немного больше. Кроме того, Теорема 4 не делает больших предположений относительно операции Heaten, так что она также может поддерживать несколько других операций на отрезках (операции с $$$t < 0$$$ невозможно доказать, так как изменения должны происходить только внутри и снаружи поддеревьев, а при $$$t < 0$$$ порядок меняется внутри поддерева).

Следующие задачи можно решить с помощью этого метода:

Codeforces 1178G. The Awesomest Vertex

Codeforces 573E. Bear and Bowling

BOJ. Неуклонное сердце 3

BOJ. Последовательность и запросы 41

Оригинал: https://koosaga.com/307 [Koosaga:Tistory]