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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
==Псевдокод==
 
==Псевдокод==
  
Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right].
+
Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right]. При этом left и right должны указывать на
  
 
   query(left, right)
 
   query(left, right)
 
       result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
 
       result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
       while left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
+
       '''while''' left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
         if (left div 2) * 2 == left // Проверяем, является ли левая граница правым сыном (индексация с 0)
+
         '''if''' (left div 2) * 2 == left // Проверяем, является ли левая граница правым сыном (индексация с 1)
 
             result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
 
             result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
 
             left = (left + 1) div 2;  
 
             left = (left + 1) div 2;  
         else
+
         '''else'''
 
             left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
 
             left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
         if (right div 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
+
         '''if''' (right div 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
 
             result = result <tex> \circ </tex> data[right];
 
             result = result <tex> \circ </tex> data[right];
 
             right = (right - 1) div 2;
 
             right = (right - 1) div 2;
         else
+
         '''else'''
 
             right = right div 2;
 
             right = right 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;
  
 
==Ссылки==
 
==Ссылки==

Версия 14:04, 3 июня 2012

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

Алгоритм

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

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

Псевдокод

Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a [math] \circ [/math] b, а результат считаем на отрезке [left, right]. При этом left и right должны указывать на

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

Ссылки

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

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

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

Алгоритм