Изменения

Рассмотрим систему координат ключ -- время.

Множество точек определяет, что происходило с деревом.

{{Определение

|definition=Множество точек называется '''древесным''' (aboral), если выполняется следующее свойство:

}}

]]

{{Теорема

|proof=

1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности.

Пусть мы обращались к какому-то ключу <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>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.

]]

Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</tex>-го запроса,

тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.

Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.

Если <tex>t != y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.

Если <tex>t = y</tex>, то есть <tex>y</tex> - предок <tex>x</tex> в момент <tex>j</tex>-го запроса,

Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.

То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника.

2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.

Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.

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

Рассмотрим наше множество точек.

Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом – время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>

]]

Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.

Рассмотрим общий случай

Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.

Обойдем эти точки.

После этого мы должны перестроить наше дерево, изменив приоритеты.

Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами.

Почему?

Предположим, что это не удалось сделать.

У нас есть вершина <tex>x</tex>, у которой есть правый сын <tex>y</tex>, и приоритет <tex>x</tex> больше чем у <tex>y</tex>, их надо поменять, то есть дотронуться до вершины <tex>y</tex>, чего мы делать не хотели в этой строке.

Но тогда рассмотрим прямоугольник(мы обращались к <tex>x</tex>)

А когда-то мы обратимся к <tex>y</tex>

Если есть точка на левой стороне, то к <tex>x</tex> мы обратимся раньше, чем к <tex>y</tex> следовательно неверно, что приоритет <tex>x</tex> больше чем приоритет <tex>y</tex>

На левой стороне точек нет.

Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.

Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к <tex>y</tex>.

Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.

Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.

Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.

}}

Таким образом, мы получили какую-то offline оптимальность.

Получим нижнюю оценку на оптимум.

Рассмотрим запросы.

Покроем их независимыми прямоугольниками.

Прямоугольники независимы, если угол одного не лежит внутри другого.

==Вторая нижняя оценка Уилберра (Wilber) ==