Реализация запроса в дереве отрезков снизу — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Алгоритм)
Строка 4: Строка 4:
 
[[Файл:Down-up1.png|right|350px|thumb|Реализация запроса снизу вверх]]
 
[[Файл:Down-up1.png|right|350px|thumb|Реализация запроса снизу вверх]]
 
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
 
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то отрезаем его и аналогично рассматриваем элемент попавший на правую границу (является ли этот элемент левым сыном). Затем поднимаемся к родителям элементов, попавших на новые границы. Отрезая элемент, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда границы пересекутся.
+
Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то отрезаем его, левая граница перемещается на один элемент вправо; в другом случае левую границу не трогаем. Аналогично рассматриваем элемент попавший на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элемент, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда границы пересекутся.
  
 
==Псевдокод==
 
==Псевдокод==

Версия 23:02, 17 мая 2011

Описание

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.

Алгоритм

Реализация запроса снизу вверх

Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).
Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то отрезаем его, левая граница перемещается на один элемент вправо; в другом случае левую границу не трогаем. Аналогично рассматриваем элемент попавший на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элемент, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда границы пересекутся.

Псевдокод

Псевдокод функции нахождения минимума на отрезке [math][left, right][/math].

  segmentMin(left, right)
     res = MAX_INT; 
     while left < right
        if left == <правый сын>
           res = min(result, data[left]);
           left = parent(left + 1);
        else
           left = parent(left);
        if right == <левый сын>
           result = min(result, data[right]);
           right = parent(right - 1);
        else
           right = parent(right);
        if left == right
           result = min(result, data[left]);
        return result;

Функция [math]parent()[/math] возвращает родителя аргумента.

Ссылки

MAXimal :: algo :: Дерево отрезков

Дерево отрезков — Википедия

Визуализатор

Алгоритм