170
правок
Изменения
Нет описания правки
|proof=
#Фазовая диаграмма работы с деревом поиска обладает свойством древестности.
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.
Рассмотрим этот прямоугольник.
На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x</tex> и <tex>y</tex> -– - вершину <tex>t</tex>.Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>х</tex> и <tex>у</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>х</tex>, значит есть точка на стороне нашего многоугольника.(Рис.2) Если <tex>t = x</tex>, то есть <tex>х</tex> -- предок <tex>у</tex> в момент <tex>i</tex>-го запроса,
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.
Обойдем эти точки.
После этого мы должны перестроить наше дерево, изменив приоритеты.
Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами
Почему?
Предположим, что это не удалось сделать.
У нас есть вершина <tex>х</tex>, у которой есть правый сын <tex>у</tex>, и приоритет у <tex>х </tex> больше чем у <tex>у</tex>, их надо поменять, то есть дотронуться до вершины <tex>у</tex>, чего мы делать не хотели в этой строке.Но тогда рассмотрим прямоугольник(мы обращались к <tex>х</tex>)А когда-то мы обратимся к <tex>у</tex>
Если есть точка на левой стороне, то к <tex>х </tex> мы обратимся раньше, чем к <tex>у </tex> следовательно неверно, что приоритет <tex>х </tex> больше чем приоритет <tex>у</tex>
На левой стороне точек нет
Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>х</tex>, но меньше <tex>у</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>у</tex>.
Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к <tex>y</tex>.
Если на верхней стороне есть точка <tex>z </tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>у</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x </tex> и <tex>z</tex>. Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны
}}
Таким образом, мы получили какую-то offline оптимальность.
Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно кол-во количество точек на диаграмме.
Получим нижнюю оценку на оптимум.
<tex>Оптимум = омега(f) </tex>Если что-то работает за <tex>O(f * g)</tex>, значит это работает не более, чем в <tex>g </tex> раз хуже.
Рассмотрим запросы.
Покроем их независимыми прямоугольниками.
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что <tex>оптимум(OPT) >= M(число запросов) + максимальное число независимых прямоугольников * 1/2</tex>==Вторая нижняя оценка Уилберра (Wilber) ==Рассмотрим запрос <tex>х</tex>Пусть левая граница <tex>= -бесконечность</tex>, правая граница <tex>= +бесконечность</tex>Идем от ключа <tex>x </tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
И каждый раз, когда встречается значение больше, чем наше, но меньше правой границы, мы сдвигаем правую границу.
Аналогично с левой границей.
Когда-то рано или поздно наши границы встретятся в <tex>х</tex>
Можно показать, что из этой оценки выходит следующая оценка
Напишем <tex>r</tex>, если меняется правая граница и <tex>l </tex> - если левая.Назовем <tex>ch(i) </tex> количество смен <tex>r </tex> на <tex>l </tex> и обратно
<tex>Оптимум >= сумме по всем запросам(i) (1 + ch(i))</tex>
Док-во упр
