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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
[[Файл:Down-up2.png‎|right|255px|thumb|Реализация запроса снизу вверх]]
+
==Алгоритм==
  
−
==Алгоритм==
+
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> \circ </tex> b.
  
−
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности.
+
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
 +
1. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей(является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева.
 +
2. Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1), пока границы не пересекутся.
 +
3. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
  
−
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Таким образом мы учтем вклад нужной нам вершины и избавимся от  вклада ненужного нам поддерева. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Продолжаем до тех пор, пока границы не пересекутся. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат, иначе {{---}} ничего делать не надо.
+
[[Файл:ДО_снизу_вверх.png‎|800px|Реализация запроса снизу вверх]]
  
 
==Псевдокод==
 
==Псевдокод==
  
−
Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).
+
Пусть результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).
  
 
   query(left, right)
 
   query(left, right)
−
       result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
+
       result = neutral;
−
       '''while''' left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
+
       '''while''' left < right
−
         '''if''' left mod 2 == 0 // Проверяем, является ли левая граница правым сыном (индексация с 0)
+
         '''if''' left mod 2 == 0
−
             result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
+
             result = result <tex> \circ </tex> data[left];
 
         left = left div 2;  
 
         left = left div 2;  
−
        // Если не является, то установим границу на родительский элемент текущей границы
+
         '''if''' right mod 2 == 1
−
         '''if''' right mod 2 == 1 // Аналогично проделываем операции с правой границей
 
 
             result = result <tex> \circ </tex> data[right];
 
             result = result <tex> \circ </tex> data[right];
 
         right = (right - 2) div 2;
 
         right = (right - 2) div 2;
−
       '''if''' left == right // После окончания цикла проверяем совпали ли границы  
+
       '''if''' left == right   
−
         result = result <tex> \circ </tex> data[left]; // Если надо пересчитываем результат
+
         result = result <tex> \circ </tex> data[left];
 
       '''return''' result;
 
       '''return''' result;
  

Версия 10:29, 10 июня 2012

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации запроса сверху вниз, итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a [math] \circ [/math] b.

Построим дерево отрезков и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа: 

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

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

Псевдокод

Пусть результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). 

  query(left, right)
     result = neutral;
     while left < right
        if left mod 2 == 0
           result = result [math] \circ [/math] data[left];
        left = left div 2; 
        if right mod 2 == 1
           result = result [math] \circ [/math] data[right];
        right = (right - 2) div 2;
     if left == right  
        result = result [math] \circ [/math] data[left];
     return result;

Ссылки

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

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

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

Алгоритм

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Реализация_запроса_в_дереве_отрезков_снизу&oldid=24681»