Изменения

}}

1) Запрос вершины 3 : вершина 3

2) Запрос 2 : вершина 3 – вершина 1 – вершина 2

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

t - наименьший общий предок х и у

]]

<tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>

|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>

Из каждой вершины будет выходить вспомогательная ссылка на корень splay-дерева, соответствующего жирному пути в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.

]]

Перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра