Изменения
Нет описания правки
|definition=
Будем называть лестницу <tex>D</tex> полностью соотносимой множеству отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не пересекает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.
}}
{{Лемма
|id=lemma1
|statement=
Если лестница <tex>D</tex> полностью соотносима множеству отрезков <tex>S</tex>, где <tex>S</tex> состоит из отрезков, пересекающих полосу <tex>\langle a, b \rangle</tex>, тогда <tex>|S| \le Ends_{a, b}(S) + |Int(D, S)|</tex>,<br>
где <tex>Ends_{a, b}(S)</tex> это число концов отрезков <tex>S</tex>, находящихся в пределах полосы <tex>\langle a, b \rangle</tex>.
}}
<tex>R \leftarrow Merge_b(Q, R’);</tex>
<tex>\}</tex>
Здесь, <tex>Merge_x(S_1, S_2)</tex> это функция объединения множеств <tex>S_1</tex> и <tex>S_2</tex>, упорядоченных по отношению <tex><_x</tex>. Время выполнения <tex>SearchInStrip</tex> эквивалентно сумме времён каждого её запуска. Очевидно, что время работы <tex>i</tex>-той функции, будет равно <tex>O(|L_i| + |Int_{a, b}(Q_i, {L_i}')|)</tex>, где <tex>L_i, Q_i, {L_i}'</tex> это соответствующие наборы <tex>(L_0 = L, L_{i+1} = {L_i}')</tex>.
Учитывая [[#lemma1|лемму]], заключаем, что функция <tex>SearchInStrip_{a, b}(L, R)</tex> работает за <tex>O(|L| + |Int_{a, b}(L)|)</tex>.
==Примечания==
