==Вторая нижняя оценка Уилберра (Wilber) ==
Рассмотрим запрос Для каждого запроса <tex>x</tex>вычислим число Уилберра.
Пусть левая граница Для ключа <tex>= -infx_[j]</tex>, правая граница рассмотрим ключи <tex>x_{i} : x_{I} = x_{j}, i = +inf0..j - 1</tex>
Идем от ключа Пусть <tex>xa_{i] < x_{j} < b_{i}</tex>, где <tex>a_{i]</tex> и <tex>b_{i}</tex> назад -- левая и ищемправая границы на момент i.Будем передвигать левую границу каждый раз, когда в предыдущий раз мы обращались к этому ключувстречаем число <tex>x_{i} : x_{i} > a, x_{i} < x </tex>. Аналогично правую.В каждый момент времени позиция <tex>a_{i]</tex> может увеличиваться, <tex>b_{i}</tex> уменьшаться.
И каждый разВыпишем последовательность : <tex>r</tex>, когда встречается значение большее, чем наше, но меньшее правой границы, мы сдвигаем правую границуесли изменяется правая граница <tex>a_{i]</tex> и <tex>l</tex> - если левая.
Аналогично с левой границейЧислом Уилберра <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
Когда-то рано или поздно наши границы встретятся в Получаем следующую оценку <tex>xOPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
Можно показать, что из этой оценки выходит следующая оценка Напишем <tex>r</tex>, если меняется правая граница и <tex>l</tex> - если левая[[Файл::DariaPicture10. Назовем <tex>ch(i)</tex> количество смен <tex>r</tex> на <tex>l</tex> и обратно <tex>OPT >= \sum\limits_{i \in [1, npng|200px]]} 1 + ch(i)</tex>
{{Теорема
