170
правок
Изменения
Нет описания правки
Можно показать, что <tex>OPT >= M</tex>(число запросов) + максимальное число независимых прямоугольников * 1/2
==Вторая нижняя оценка Уилберра (Wilber) ==
Рассмотрим запрос <tex>хx</tex>
Пусть левая граница <tex>= -inf</tex>, правая граница <tex>= +inf</tex>
Идем от ключа <tex>x</tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
И каждый раз, когда встречается значение большебольшее, чем наше, но меньше меньшее правой границы, мы сдвигаем правую границу.
Аналогично с левой границей.
Когда-то рано или поздно наши границы встретятся в <tex>x</tex>
<tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!там
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что сумма по всем i (ch(i)) >= сумма по i изменения числа жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
===Пример===
Пусть изначально все левые ребра были жирными.
Операций первого становления ребра жирным <tex>O(n) </tex> – дают не существенный вклад в асимптотику.
Глубина нашего дерева logn<tex>log n</tex>
Из каждой вершины выходит <= 2 ребер
В общем случае одно жирное, другое нет
Таким образом, все наши ключи организуют иерархичную структуру.
Каждый жирный путь -- splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)
Время работы (M + число изменений жирных ребер) * <tex> log log n</tex>
Поиск
Поиск ключа <tex>x</tex>
Ищем в корне tango-дерева – splay-дереве.
Если не нашли, значит надо идти по нежирному ребру.
Пойдем по нему(красная стрелка) и ищем в новом дереве.
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = <tex>log n</tex>) = <tex>log log n</tex>
Поиск во всем дереве = <tex>(log log n) </tex> * число проходов по нежирному ребру.
Перестройка дерева
// Как обратно вставить 9 10
Merge в splay-дереве.
<tex>T1<T2 </tex> сливаем в <tex>T, T1 </tex> – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем <tex>Т2</tex>.
Но у нас <tex>Т1 </tex> не меньше <tex> Т2</tex>
Посмотрим на общий случай
Был жирный путь
Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли.
Перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за loglogn <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n)) </tex> * число изменений жирного ребра
