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

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

Версия 22:06, 8 мая 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 :: Дерево отрезков

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

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

Алгоритм