170
правок
Изменения
м
Для ключа <tex>x_{j}</tex> рассмотрим ключи Рассмотрим запросы <tex>x_{i} : \{x_{i} = x_{j}, i = 0..j - 1\}</tex>
→Вторая нижняя оценка Уилбера (Wilber)
==Вторая нижняя оценка Уилбера (Wilber) ==
Для каждого запроса <tex>xx_{j}</tex> вычислим число Уилбера.
Пусть <tex>a < x_{j} < b</tex>, где <tex>a</tex> и <tex>b</tex> {{---}} левая и правая границы на момент <tex>i</tex>.
На момент времени <tex> i = 0 : a = -\infty, b = +\infty</tex>.
Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i} : \{a < x_{ij} < x_{ji}< a\} </tex>. Аналогично правую.
В каждый момент времени позиция <tex>a</tex> может увеличиваться, <tex>b</tex> уменьшаться.
Рано или поздно, наши границы <tex>a</tex> и <tex>b</tex> встретятся в <tex>x_{i} = x_{j}</tex>
Напишем <tex>r</tex>, если изменяется правая граница <tex>b</tex> и <tex>l</tex> {{---}} если левая.
Получаем следующую оценку
<tex>OPT \geqslant \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(i)</tex> множество попарно независимых прямоугольников.
[[Файл:DariaPicture11.png|300px]]
