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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 10 участников)
Строка 1: Строка 1:
==Описание==
 
Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.
 
 
==Алгоритм==
 
==Алгоритм==
[[Файл:Down-up1.png|right|350px|thumb|Реализация запроса снизу вверх]]
+
 
Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br>
+
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.
Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то отрезаем его, левая граница перемещается на один элемент вправо; в другом случае левую границу не трогаем. Аналогично рассматриваем элемент попавший на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элемент, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда границы пересекутся.
+
 
 +
[[Дерево отрезков. Построение|Построим дерево отрезков]], и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
 +
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от  вклада ненужного нам поддерева.
 +
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.
 +
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
 +
 
 +
{| 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]]
 +
|}
  
 
==Псевдокод==
 
==Псевдокод==
Псевдокод функции нахождения минимума на отрезке <tex>[left, right]</tex>.
 
  
   segmentMin(left, right)
+
Пусть результат считаем на отрезке <tex> [left, right] </tex>. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.
       res = MAX_INT;
+
 
       while left < right
+
   '''int''' query(left: '''int''', right: '''int'''):
         if isRightSon(left)
+
       leftRes = ''neutral''
             res = min(res, data[left]);
+
       rightRes = ''neutral''
            left = parent(left + 1);
+
      '''while''' left < right
         else
+
         '''if''' left '''mod''' 2 == 0
            left = parent(left);
+
             leftRes = leftRes <tex> \circ </tex> data[left]
         if isLeftSon(right)
+
         left = left '''div''' 2
             res = min(res, data[right]);
+
         '''if''' right '''mod''' 2 == 1
            right = parent(right - 1);
+
             rightRes = data[right] <tex> \circ </tex> rightRes
        else
+
        right = right '''div''' 2 - 1
            right = parent(right);
+
      '''if''' left == right
        if left == right
+
        leftRes = leftRes <tex> \circ </tex> data[left]
            res = min(res, data[left]);
+
      '''return''' leftRes <tex> \circ </tex> rightRes
        return res;
 
  
Функция <tex>parent()</tex> возвращает родителя аргумента.<br>
+
==См. также==
Функции <tex>isLeftSon(), isRightSon()</tex> возвращают является ли элемент правым или левым сыном соответственно.
+
* [[Реализация запроса в дереве отрезков сверху]]
Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.
 
  
  parent(vertex)
+
==Источники информации==
      return vertex / 2;
 
  
  isLeftSon(vertex)
+
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
      if parent(vertex) * 2 + 1 == vertex
 
        return true;
 
      return false;
 
  
==Ссылки==
+
* [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

См. также

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