333
правки
Изменения
→Алгоритм
==Алгоритм==
''Замечание.''Используем в алгоритме не отрезки, а полуинтервалы(левая граница включительно, а правая - нет). Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на отрезке полуинтервале <tex>[a .. b])</tex>.
[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков]]
* <tex>node</tex> {{---}} номер(в массиве с деревом отрезков) текущей вершины дерева.
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого отрезкаполуинтервала.
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы отрезковполуинтервала, за которые "отвечает" наша вершина, причем левые границы обоих отрезков - включительно, а правые - нет. В дальнейшем будем называть подобную структуру полуинтверваломвершин.
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
