170
правок
Изменения
Нет описания правки
{{Гипотеза
|statement=[http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево ''Splay''] деревья обладают динамической оптимальностью.
То есть если мы разрешаем перестраивать деревья в процессе запроса, то ''splay-'' деревья не больше, чем в константу хуже оптимальных.
Время работы ''splay'' дерева <tex>O(OPT dyn)</tex>
}}
Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
[[Файл:DariaPicture2.png|thumb|300px| t -- наименьший общий предок х и у
]]
Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</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>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>
[[Файл:DariaPicture3.png|thumb|300px| Построение декартова дерева
В каждый момент времени позиция <tex>a_{i}</tex> может увеличиваться, <tex>b_{i}</tex> уменьшаться.
Напишем <tex>r</tex>, если изменяется правая граница <tex>b_{i}</tex> и <tex>l</tex> -- если левая.
Числом Уилбера <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >= <tex>\sum\limits_{i \in [1, n]}K</tex> изменения числа , где <tex>K</tex> -- число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
{{Определение
|definition='''Танго дерево''' -- online бинарное дерево поиска с временем работы <tex> O(\log \log N) </tex>, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.
Лучшая известная реализация на данный момент.
}}
{{Определение
|definition='''Жирное ребро'''(''Prefered Path'') -- ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
]]
Каждый из этих жирных путей организуем в свое ''splay-'' дерево.
Из каждой вершины создадим вспомогательную ссылку на корень ''splay'' дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.
Глубина ''tango'' дерева <tex>\log n</tex>.
Время работы <tex>(M + число изменений жирных реберK) *<tex> \log \log n</tex>, где <tex>K</tex> -- число изменений жирных ребер.
<font color=green>Операций первого становления ребра жирным -- ''O(\log n)'', это дает несущественный вклад в асимптотику. </font>
