Изменения
Нет описания правки
<tex>Split_{a,b}(L, Q, L')</tex>
<tex>\{</tex>
<tex>L' \leftarrow 0\varnothing; Q \leftarrow 0\varnothing</tex>
'''For''' <tex>j = 1,...,k</tex> '''do'''
'''if''' отрезок <tex>S_j</tex> не пересекает
добавить <tex>s_j</tex> в конец <tex>L’;</tex>
<tex>\}</tex>
Эта функция работает за <tex>O(|L|)</tex> времени.
===Search In Strip===
Зная <tex>L</tex> мы можем найти <tex>Int_{a, b}(L)</tex> и <tex>R</tex> используя следующую рекурсивную функцию:
<tex>SearchInStrip_{a, b}(L, R)</tex>
<tex>\{</tex>
<tex>Split(L, Q, L');</tex>
'''if''' <tex>L' = \varnothing</tex> '''then'''
<tex>R \leftarrow Q;</tex>
'''return'''<tex>;</tex>
Найдем <tex>Int_{a, b}(Q, L');</tex>
<tex>SearchInStrip_{a, b} (L', R');</tex>
<tex>R \leftarrow Merge_b(Q, R’);</tex>
<tex>\}</tex>
==Примечания==
