Введение 3
Постановка задачи 4
1. Обзор литературы 5
2. Постановка решаемой задачи 6
3. Пререквизиты 8
4. Основная идея 11
5. Знакомство с Segment Tree Beats на примере задачи mod =, = в
точке, Р 13
5.1. Формулировка 13
5.2. Алгоритм 13
5.3. Оценка времени работы 14
6. Ji Driver Segment Tree (min =, ^2) 19
6.1. Формулировка 19
6.2. Решение 19
6.3. Доказательство 21
7. Extended Ji Driver Segment Tree (min =, + =, £) 25
7.1. Формулировка 25
7.2. Решение 25
7.3. Доказательство 25
7.4. Улучшенная оценка 29
8. GCD Ji Driver Segment Tree (min =, + =, gcd) 35
8.1. Формулировка 35
8.2. Решение + доказательство упрощенной версии задачи .... 35
8.3. Решение + доказательство полной версии задачи 38
9. mod =, = на отрезке, 41
9.1. Формулировка 41
9.2. Решение 41
9.3. Доказательство 41
10. .р =, + =, =, P 44
10.1. Формулировка 44
10.2. Решение 44
10.3. Доказательство 46
10.4. Улучшенная оценка 48
11. / =, + =, =, P 51
11.1. Формулировка 51
11.2. Решение 51
11.3. Доказательство 52
11.4. Улучшенная оценка 53
12. Сценарии применения в реальной жизни 56
Заключение 58
Список литературы 60
Задача поиска значения какой-то функции на отрезке массива является одной из наиболее стандартных и широко изученных проблем в теоретической информатике. Одна из самых известных работ в этой области — статья Фараха-Колтона и Бендера [1], решающая задачу поиска минимума на отрезке за оптимальное время. Кроме того, во многих контекстах бывает необходимо решать так называемые «динамические» версии этих задач, то есть при условии, что элементы массива могут меняться со временем. Широко исследованы такие запросы изменения как прибавление константы ко всем элементам на отрезке и присвоение какой-то константы всем элементам на отрезке. Для решения этих задач применяются такие стандартные структуры данных как дерево отрезков и дерево Фенвика [2]. Однако какие-либо запросы изменения кроме этих двух стандартных были всегда обделены вниманием из-за того, что не удавалось придумать алгоритмов, которые бы работали столь же быстро, как и обычные деревья отрезков.
Большой шаг в эту стороны был сделан Ruyi Ji в 2016 году в его полу- научной статье [3]. К сожалению, в полном виде этот текст доступен только на китайском языке и с достаточно большим количеством неформальностей и допущений. Цель моей работы — воспроизведение результатов Ruyi Ji, их формализация, а также улучшение полученных оценок в уже рассмотренных задачах и применение схожих методов для решения новых задач. Центральной темой моей работы является так называемая задача «min =»: запрос изменения, заменяющий все элементы на отрезке на минимум из текущего значения и константы. Этот запрос, пожалуй, является наиболее естественным запросом изменения кроме стандартных: прибавления и присвоения на отрезке. Кроме того, в работе я не только исследовал теоретическую сложность, но и реализовал и протестировал решения всех исследуемых задач на языке программирования C++. Также, в этой работе я привожу сценарии использования проанализированных мною алгоритмов для решения задач из реальной жизни: к примеру, поддержка актуальной стоимости ценной бумаги на фондовом рынке при появляющихся и пропадающих предложениях.
В данной работе были исследованы алгоритмы из семейства Segment Tree Beats, получены улучшенные оценки на время работы для задач Extended Ji Driver Segment Tree, GCD Ji Driver Segment Tree, а также задач с запросами взятия квадратного корня и деления нацело на отрезке. А именно:
• Для задач семейства Ji Driver Segment Tree были более точно сформулированы асимптотики.
• Для задачи Extended Ji Driver Segment Tree асимптотика была улучшена с O(n log n + q log2 n) до O(n log n + q1 log n + q2 log2 n + q3 log n).
• Для задачи с запросами min = и gcd асимптотика была улучшена с O((n + q) logn log C) до O((n + q)(logn + log C)).
• Для задачи GCD Ji Driver Segment Tree асимптотика была улучшена с O(nlognlogC + qlog2nlogC) до O((n + qlogn)(logn + logC)) и O((n + q1 + q2 logn + q3)(logn + logC)), если быть еще точнее.
• Для задачи с запросами p =, + =, = и 52 асимптотика была улучшена с O((n + q log n) log C) до O((n + q log n) log log C).
• Для задачи с запросами / =, + =, = и 52 при условии, что деление производится на числа, не меньшие к, асимптотика была улучшена с O((n + q logn) log C) до O((n + q logn) logk C).
Кроме того, были написаны реализации представленных алгоритмов на языке C++, а также разработаны сценарии применения предложенных алгоритмов на практике.
Продолжением исследования может быть дальнейшее изучение задачи Extended Ji Driver Segment Tree в надежде приравнять теоретическую верхнюю и нижнюю оценки на время работы (что, как следствие, может приравнять эти оценки и для задачи GCD Ji Driver Segment Tree), а также анализ новых задач, для которых может быть применима парадигма Segment Tree Beats.
Кроме того хочется прокомментировать несколько подходов к дальнейшему изучению задачи Extended Ji Driver Segment Tree:
• Одним из возможных направлений в исследовании может быть изучение вопроса о времени работы при условии, что входные данные сгенерированы случайно (в соответствии с каким-то распределением). Это потенциально может помочь для доказательства логарифмического времени работы.
• В общем случае можно считать, что все запросы выполняются не на отрезках массива, а на префиксах. Действительно, сумма на отрезке — это разность сумм префиксов, прибавление на отрезке можно выразить через прибавление на префиксе правой границы и вычитание на префиксе левой границы, а операцию min = на отрезке можно выразить как вычитание большой константы на префиксе левой границы, применение операции min = на префиксе правой границы и обратное прибавление большой константы на префиксе левой границы. Возможно, в силу большей простоты операции прибавления на префиксе, это может как-то помочь в анализе алгоритма.
• Хранить кроме первого и второго максимума на отрезке еще и третий, четвертый и так далее кажется бесполезным. Безусловно, хранить их можно, однако это не поможет нам ослабить условие tagCondition. Все еще если x < secondMax, мы не можем пересчитать значения в данной вершине, ведь в этом случае второй максимум стал первым, третий стал вторым, и так далее. Тогда если мы храним к максимумов, то к-й максимум стал к — 1-м, а к + 1-й стал k-м, но к + 1-й максимум мы не храним и не имеем возможности легко его найти. Аналогичная проблема возникает при попытке пересчитать количества максимумов.
