77
правок
Изменения
→Построение дерева и запрос операции
Рассмотрим алгоритм построения сжатого дерева отрезков на следующем примере:<br>[[Файл:set_a.png]]
* Cоставить Cоставим массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочить упорядочим его по первой координате* Построить , построим на нём дерево отрезков с сохранением подмассива в каждой вершине[[Файл:tree_built.jpg]]
* Все подмассивы в вершинах получившегося дерева отрезков упорядочить по следующей координате, после чего повторить построение дерева для каждого из них
<br>
