170
правок
Изменения
→Вторая нижняя оценка Уилбера (англ. Wilber)
Для каждого запроса <tex>x</tex> вычислим число Уилбера.
Для ключа <tex>x_[{j]}</tex> рассмотрим ключи <tex>x_{i} : x_{I} = x_{j}, i = 0..j - 1</tex>
Пусть <tex>a_{i} < x_{j} < b_{i}</tex>, где <tex>a_{i}</tex> и <tex>b_{i}</tex> {{---}} левая и правая границы на момент i.
Напишем <tex>r</tex>, если изменяется правая граница <tex>b_{i}</tex> и <tex>l</tex> -- если левая.
{{Определение|definition=Числом Уилбера <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.}}
Получаем следующую оценку
