170
правок
Изменения
Нет описания правки
Лучшая известная реализация на данный момент.
Время работы tango-дерева <tex>O(OPT dyn * \cdot \log \log n)</tex>
==Динамическая оптимальность==
===Модель оптимального дерева===
Рассмотрим ключи <tex>1..n</tex> и запросы <tex>x_{1}..x_{n}</tex>, где <tex>x_{i} \in \{1..n\}</tex> {{– --}} ключ, к которому мы обращаемся.
{{Утверждение
Рассмотрим этот прямоугольник.
На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x</tex> и <tex>y</tex> {{---}} вершину <tex>t</tex>.
Если <tex>t != \ne x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
[[Файл:DariaPicture2.png|thumb|300px| t {{---}} наименьший общий предок х и у
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
Если <tex>t != \ne y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
Если <tex>t = y</tex>, то есть <tex>y</tex> {{---}} предок <tex>x</tex> в момент <tex>j</tex>-го запроса,
Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.
<tex>OPT(x) = \Omega(f) </tex>
<font color=green>Если что-то работает за ''O(f * \cdot g)'', значит это работает не более, чем в ''g'' раз хуже.</font>
Рассмотрим запросы.
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что <tex>OPT(x) >= M + 1 MP /2* MP</tex>, где <tex>M</tex> {{---}} число запросов, <tex>MP</tex> {{---}} максимальное число независимых прямоугольников.
То есть <tex>OPT(x) = \Omega(M + 1MP /2* MP)</tex>
==Вторая нижняя оценка Уилбера (англ. ''Wilber'') ==
Глубина tango-дерева <tex>\log n</tex>.
Время работы <tex>(M + K) * \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
<font color=green>Операций первого становления ребра жирным {{---}} ''O(\log n)'', это дает несущественный вклад в асимптотику. </font>
Таким образом,
перестройка = <tex>3 * \cdot split + 3 * \cdot merge = (O(1) + 3*\cdot O(\log \log n) + 3*\cdot O(\log \log n)) * \cdot K</tex>, где <tex>K</tex> {{---}} число изменений жирного ребра.
