Курсовая работа: Улучшение оценок времени работы алгоритмов Segment Tree Beats

Содержание

• Основнаяидея.............................. 11

• Знакомство с Segment Tree Beats на примере задачи mod =, = в

• Ji Driver Segment Tree (min =, ^P) . . . . . . . . . . . . . . . . . . . 19 6.1.Формулировка.......................... 19

• GCD Ji Driver Segment Tree (min =, + =, gcd) . . . . . . . . . . . . 35 8.1.Формулировка.......................... 35

8.2. Решение + доказательство упрощенной версии задачи . . . . 35

8.3. Решение + доказательство полной версии задачи . . . . . . . 38

2

• ==,+=,=,P.............................. 51 11.1.Формулировка.......................... 51

• Сценарии применения в реальной жизни . . . . . . . . . . . . . . 56Заключение................................. 58 Списоклитературы ............................ 60

3

Введение

Задача поиска значения какой-то функции на отрезке массива является одной из наиболее стандартных и широко изученных проблем в теоретиче-ской информатике. Одна из самых известных работ в этой области — статья Фараха-Колтона и Бендера [1], решающая задачу поиска минимума на отрезке за оптимальное время. Кроме того, во многих контекстах бывает необходимо решать так называемые «динамические» версии этих задач, то есть при усло-вии, что элементы массива могут меняться со временем. Широко исследованы такие запросы изменения как прибавление константы ко всем элементам на отрезке и присвоение какой-то константы всем элементам на отрезке. Для решения этих задач применяются такие стандартные структуры данных как дерево отрезков и дерево Фенвика [2]. Однако какие-либо запросы измене-ния кроме этих двух стандартных были всегда обделены вниманием из-за того, что не удавалось придумать алгоритмов, которые бы работали столь же быстро, как и обычные деревья отрезков.

Большой шаг в эту стороны был сделан Ruyi Ji в 2016 году в его полу-научной статье [3]. К сожалению, в полном виде этот текст доступен