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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 1: Строка 1:
 
==Алгоритм==
 
==Алгоритм==
  
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> \circ </tex> b.
+
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.
  
 
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
 
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
Строка 22: Строка 22:
 
==Псевдокод==
 
==Псевдокод==
  
Пусть результат считаем на отрезке [left, right]. При этом значения left и right, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные left_res и right_res будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.  
+
Пусть результат считаем на отрезке [<tex> left, right </tex>]. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>left</tex>_<tex>res</tex> и <tex>right</tex>_<tex>res</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.  
  
 
   '''int''' query(left : '''int''', right : '''int'''):
 
   '''int''' query(left : '''int''', right : '''int'''):

Версия 10:45, 13 июня 2014

Алгоритм

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

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

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

Псевдокод

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

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

Ссылки

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

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

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

Алгоритм