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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
   Min(left, right)
 
   Min(left, right)
 
       result = +inf; //Присваиваем результату максимально возможное значение
 
       result = +inf; //Присваиваем результату максимально возможное значение
       while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут
+
       while left < right //Выполняем цикл до тех пор пока левая и правая граница не совпадут
         if ((left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном
+
         if (left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном
             result = min(result, left.data); // Если является то пересчитаем результат и перенесем левую границу
+
             result = min(result, data[left]); // Если является то пересчитаем результат и перенесем левую границу
 
             left = (left + 1) / 2;  
 
             left = (left + 1) / 2;  
 
         else
 
         else
 
             left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы
 
             left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы
         if ((right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
+
         if (right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
             result = min(result, right.data);
+
             result = min(result, data[right]);
 
             right = (right - 1) / 2;
 
             right = (right - 1) / 2;
 
         else
 
         else
 
             right = (right) / 2;
 
             right = (right) / 2;
       if (left == right) // После окончания цикла проверяем совпали ли границы   
+
       if left == right // После окончания цикла проверяем совпали ли границы   
         result = min(result, left.data); // Если надо пересчитываем результат
+
         result = min(result, data[left]); // Если надо пересчитываем результат
 
       return result;
 
       return result;
  
Строка 33: Строка 33:
 
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
 
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
  
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2  Дерево отрезков — Википедия]
+
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2  Википедия {{---}} Дерево отрезков]
  
 
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]
 
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]
  
 
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]
 
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]
 +
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Дерево отрезков]]

Версия 14:53, 24 мая 2012

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

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения(RMQ).

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

Псевдокод

Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.

  //Функция нахождения минимального элемента на отрезке [math][left, right][/math]
  Min(left, right)
     result = +inf; //Присваиваем результату максимально возможное значение
     while left < right //Выполняем цикл до тех пор пока левая и правая граница не совпадут
        if (left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном
           result = min(result, data[left]); // Если является то пересчитаем результат и перенесем левую границу
           left = (left + 1) / 2; 
        else
           left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы
        if (right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
           result = min(result, data[right]);
           right = (right - 1) / 2;
        else
           right = (right) / 2;
     if left == right // После окончания цикла проверяем совпали ли границы  
        result = min(result, data[left]); // Если надо пересчитываем результат
     return result;

Ссылки

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

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

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

Алгоритм