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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
==Алгоритм==
 
==Алгоритм==
  
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> \circ </tex> b.
+
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.
  
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
+
[[Дерево отрезков. Построение|Построим дерево отрезков]], и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
 
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от  вклада ненужного нам поддерева.  
 
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от  вклада ненужного нам поддерева.  
 
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.
 
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.
 
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
 
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
  
[[Файл:ДО_снизу_вверх.png‎|800px|Реализация запроса снизу вверх]]
+
{| cellpadding="10"
 +
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''
 +
|-
 +
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]
 +
|-
 +
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]
 +
|-
 +
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]
 +
|-
 +
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]
 +
|}
  
 
==Псевдокод==
 
==Псевдокод==
  
Пусть результат считаем на отрезке [left, right]. При этом значения left и right, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).
+
Пусть результат считаем на отрезке <tex> [left, right] </tex>. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.  
  
   query(left, right)
+
   '''int''' query(left: '''int''', right: '''int'''):
       result = neutral;
+
       leftRes = ''neutral''
 +
      rightRes = ''neutral''
 
       '''while''' left < right
 
       '''while''' left < right
         '''if''' left mod 2 == 0
+
         '''if''' left '''mod''' 2 == 0
             result = result <tex> \circ </tex> data[left];
+
             leftRes = leftRes <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];
+
             rightRes = data[right] <tex> \circ </tex> rightRes
         right = (right - 2) div 2;
+
         right = right '''div''' 2 - 1
 
       '''if''' left == right   
 
       '''if''' left == right   
         result = result <tex> \circ </tex> data[left];
+
         leftRes = leftRes <tex> \circ </tex> data[left]
       '''return''' result;
+
       '''return''' leftRes <tex> \circ </tex> rightRes
  
==Ссылки==
+
==См. также==
 +
* [[Реализация запроса в дереве отрезков сверху]]
  
[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://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
  
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]
+
* [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/algorithm Алгоритм]
+
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]
  
 +
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]

Текущая версия на 19:18, 4 сентября 2022

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации запроса сверху вниз, итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее [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]leftRes[/math] и [math]rightRes[/math] будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.

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

См. также

Источники информации