Изменения

Перейти к: навигация, поиск

Дерево отрезков. Построение

49 байт добавлено, 22:20, 26 апреля 2011
Структура
==Структура==
[[Файл:Segment_tree.jpg|right|400px|thumb|Пример дерева отрезков для вычисления сумм]]Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по 2 ребёнка и содержат сумму или минимум/максимум своих детей (в зависимости от поставленной задачи). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0...n-1]</tex>, левый ребёнок корня содержит результат функции на <tex>[0...n/2]</tex>, а правый, соответственно результат на <tex>[n/2+1...n-1]</tex>. И так далее, продвигаясь вглубь дерева.
<br><br><br><br><br><br><br><br><br><br><br><br>
==Построение дерева==
Анонимный участник

Навигация