==Асимптотика==
===Запрос===
Запрос производится за время пропорцианальное глубине графа(поисковой структуры). Если считать, что на каждой итерации глубина увеливается максимум на 3, то время работы в худшем случаи будет O(3n). Но мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случай. Рассмотрим путь пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов созданных на итерации i. Эта величина зависит только от порядка добаления отрезков(если множество установлено). Будет искать математическое ожидание глубины графа. <tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex> Считая, что <tex> P_i </tex> - вероятность того, что на i-ой итерации был добавлен узел.
<tex>\sum^{n}_{i=1}E[X_i]</tex> <= \sum^{n}_{i=1}3P_i</tex>
Наша задача, понять чем ограничена <tex>P_i<tex>.
Пусть <tex> \Delta_q(i) </tex> - трапецоид содержащий q на i-ой итерации.
Скажем, что произошло изменение на i-ой итерации если <tex> \Delta_q(i) </tex> != <tex> \Delta_q(i - 1) </tex> Таким образом P_i = P(<tex> \Delta_q(i) </tex> != <tex> \ne \Delta_q(i - 1) </tex>). Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид <tex> \Delta_q(i) </tex> был одним из созданных при моификации. Заметим, что все трапецоиды созданные на этой итерации были смежны текущему отрезку. Либо этот отрезок был top или bottom, либо его концы были leftp или rightp.
Представим, что наш трапецоид <tex> \Delta_q(i) </tex> исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...). Рассмотрим вероятность этого исчезновения. Так как отрезки мы добавляли в рандомном порядке, вероятность текущему отрезку быть top или bottom равна 1/i. leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1/i. Аналогично для rightp.
Таким образом P_i = P(<tex> \Delta_q(i) </tex> \ne <tex> \Delta_q(i - 1) </tex>) = P(<tex> \Delta_q(i) </tex> \in <tex> \Delta_q(i - 1) </tex>) <= 4/i
<tex>\sum^{n}_{i=1}E[X_i]</tex> <= <tex>\sum^{n}_{i=1}3P_i <= \sum^{n}_{i=1}12/i <=12\sum^{n}_{i=1}(1/i) \approx 12*log(n)</tex>
<tex>\sum^{n}_{i=1}E[X_i]</tex> <= \sum^{n}_{i=1}3P_i</tex> <= <tex>\sum^{n}_{i=1}12/i <=12\sum^{n}_{i=1}(1/i) \approx 12*log(n)</tex> Ура
