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