170
правок
Изменения
Нет описания правки
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что <tex>OPT(x) >= \geqslant M + MP / 2</tex>, где <tex>M</tex> {{---}} число запросов, <tex>MP</tex> {{---}} максимальное число независимых прямоугольников.
То есть <tex>OPT(x) = \Omega(M + MP / 2)</tex>
Получаем следующую оценку
<tex>OPT >= \geqslant \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
[[Файл:DariaPicture11.png|300px]]
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >= \geqslant <tex>\sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = <tex>\log n</tex>) = <tex>\log \log n</tex>.
Поиск во всем дереве = <tex>(\log \log n)\cdot </tex> * число проходов по нежирному ребру.
====Пример====
