133
правки
Изменения
→Построение дерева
==Построение дерева==
Рассмотрим алгоритм построения сжатого дерева отрезков на следующем примере:<br>[[Файл:set_a.png]]
<tex>
p=2, A:
\begin{cases}
(1, 3), \mbox{weight}=7 \\
(2, 1), \mbox{weight}=1 \\
(3, 3), \mbox{weight}=8 \\
(4, 2), \mbox{weight}=5
\end{cases}
</tex>
* Cоставим массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочим его по первой координате, построим на нём дерево отрезков с сохранением подмассива в каждой вершине<br>[[Файл:tree_built.png]]
