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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
м (rollbackEdits.php mass rollback)
 
(не показано 69 промежуточных версий 11 участников)
Строка 1: Строка 1:
Данная рекурсивная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.
+
Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.
  
 
==Алгоритм==
 
==Алгоритм==
 +
''Замечание.''
 +
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).
  
==Пример==
+
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a \ldots b)</tex>.
Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке), то есть пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] построенное дерево отрезков и задача найти сумму на отрезке <tex>[a .. b]</tex>.
+
 
[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]
+
В качестве параметров рекурсий передаем следующие переменные:
 +
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.
 +
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.
 +
 
 +
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.
 +
Запустим рекурсивную процедуру от всего полуинтервала  (то есть от корневой вершины).
 +
 
 +
Для текущего состояния проверяем следующие условия:
  
Будем передавать в качестве параметров рекурсий следующие переменные:
+
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
* <tex>node</tex> {{---}} номер(в массиве с деревом отрезков) текущей вершины дерева.
+
:''Например'': текущий <tex>[1 \ldots 3)</tex>, а искомый <tex>[3 \ldots 5)</tex>;
* <tex>l</tex>, <tex>r</tex> {{---}} левая и правая границы отрезков, за которые "отвечает" наша вершина.
 
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого отрезка.
 
  
Запустим рекурсивную процедуру от всего отрезка(то есть от корневой вершины).
+
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
 +
:''Например'': текущий <tex>[2 \ldots 3)</tex>, а искомый <tex>[2 \ldots 4)</tex>;
  
Для текущего состояния проверяем следующие условия :
+
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
  
* Если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.
+
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.
''Например'': текущий <tex>[1..2]</tex>, а искомый <tex>[3 .. 4]</tex>;
 
  
* Текущий отрезок совпадает, то возвращаем значение в текущей вершине.
+
==Пример==
''Например'': текущий и искомый <tex>[2..3]</tex>;
 
  
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом сумма на текущем отрезке равна сумме результатов функций, запущенных от детей.  
+
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
''Замечание:''
 
  
При передаче новых параметров следует изменять не только границы, за которые отвечает текущая вершина, но и границы запрашиваемого отрезка, чтобы на последующих шагах произошло полное совпадение отрезков.
+
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.
  
Так как каждый отрезок разбивается не более, чем на <tex>O(\log n)</tex> отрезков (поскольку на каждом уровне дерева может быть не более двух отрезков из разбиения, а всего уровней <tex>\log n</tex> ), то данная реализация выполняется за <tex>O(\log n)</tex>.
+
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
 +
{{---}} это отрезок <tex>[1 \ldots 4]</tex> (полуинтервал <tex>[1 \ldots 5)</tex>).
 +
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]
 +
Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):
  
[[Файл:Шагал1538.JPG|right|380px|thumb|Дерево отрезков]]
+
* На глубине <tex>0</tex>.
 +
** Текущий полуинтервал <tex>[0 \ldots 8)</tex> пересекается с <tex>[1 \ldots 5) \Rightarrow</tex> рекурсивно переходим к <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex>
  
'''Например''' рассмотрим работу программы на дереве отрезков для элементов <tex>[1 .. 8]</tex>.
 
Пусть запрашиваемая сумма - это отрезок <tex>[2 .. 5]</tex>.
 
  
*Текущий отрезок <tex>[1 .. 8]</tex>, он больше <tex>[2 .. 5]</tex> => переходим по рекурсивным вызовам на <tex>[1 .. 4]</tex> и <tex>[5 .. 8]</tex>
+
* На глубине <tex>1</tex>.  
 +
** <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex> пересекаются с <tex> [1 \ldots 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 \ldots
 +
2)</tex>, <tex>[2 \ldots 4)</tex>, <tex>[4 \ldots 6)</tex> и <tex>[6 \ldots 8)</tex>
  
  
*<tex>[1 .. 4]</tex> выходит за границы<tex> [2 .. 5]</tex>, <tex>[5 .. 8]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим по рекурсивным вызовам на <tex>[1 .. 2]</tex>, <tex>[3 .. 4]</tex> и <tex>[5 .. 6]</tex>, <tex>[7 .. 8]</tex>.
+
* На глубине <tex>2</tex>.
 +
** <tex>[0 \ldots 2)</tex> и <tex>[4 \ldots 6)</tex> пересекаются с  <tex>[1 \ldots 5) \Rightarrow </tex> переходим в листья <tex>[0 \ldots 1), [1 \ldots 2), [4 \ldots 5), [5 \ldots 6) </tex>
 +
** <tex>[2 \ldots 4) </tex> полностью лежит внутри <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
 +
** <tex>[6 \ldots 8)</tex> не пересекается с <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем нулевое значение
  
  
*<tex>[1 .. 2]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим в листья 1, 2;  <tex>[3 .. 4]</tex> целиком внутри <tex>[2 .. 5]</tex> => возвращаем значение в <tex>[3 .. 4]</tex>; <tex>[7 .. 8]</tex> не пересекается с <tex>[2 .. 5]</tex> => возвращаем нулевое значение, <tex>[5 .. 6]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим к листьям <tex>5</tex> и <tex>6</tex>
+
* На глубине <tex>3</tex>.
 +
** Листья <tex>[1 \ldots 2), [4 \ldots 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
 +
** Листья <tex>[0 \ldots 1), [5 \ldots 6)</tex> лежат вне <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем нейтральное значение
  
*лист <tex>6</tex> не пересекается с отрезком <tex>[2 .. 5]</tex> => возвращаем нулевое значение, лист <tex>5</tex> целиков внутри <tex>[2 .. 5]</tex> => возвращаем значение в листе <tex>5</tex>.
+
Таким образом ответ на полуинтервале <tex>[1 \ldots 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2)</tex>, <tex>[2 \ldots 4)</tex> и <tex>[4 \ldots 5)</tex>.
  
 
==Реализация==
 
==Реализация==
Рассмотрим реализацию рассматриваемой выше задачи RSQ.
+
Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.
<code>
 
  
  int get_sum (int node, int a, int b)
+
Пусть в узлах дерева хранятся структуры из трех полей:
  {
+
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
        l = tree[node].left;
+
* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.
        r = tree[node].right;
+
* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.
        // [l, r)
 
        if [l, r) <tex>\bigcap</tex> [a, b) == <tex> \varnothing</tex>
 
            return 0;
 
        if [l, r) == [a, b)
 
            return tree[node];
 
        int m = (l + r) / 2;
 
        return get_sum (node * 2 + 1, a, min(b, m))
 
            + get_sum (node * 2 + 2, max(a, m), b);
 
  }  
 
</code>
 
  
==Ссылки==
+
  '''int''' query('''int''' node, '''int''' a, '''int''' b)   
 +
      l = tree[node].left
 +
      r = tree[node].right
 +
      '''if''' [l, r) <tex>\cap </tex> [a, b) == <tex>\varnothing</tex>
 +
          '''return''' ''<tex>\varepsilon</tex>''                    <span style="color:#008000">// <tex>\varepsilon</tex> {{---}} нейтральный для данной операции элемент</span>
 +
      '''if''' [l, r) <tex>\subset</tex> [a, b)
 +
          '''return''' tree[node].res
 +
      '''return''' query(node * 2 + 1, a, b) <tex> \circ </tex> query(node * 2 + 2, a, b)
  
[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://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 Визуализатор дерева отрезков]
+
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]

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

Данная операция позволяет выполнять запросы на дереве отрезков, причем алгоритм запускается от корня и рекурсивно идет сверху вниз.

Алгоритм

Замечание. Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая — нет).

Пусть есть уже построенное дерево отрезков и идет запрос на полуинтервале [math][a \ldots b)[/math].

В качестве параметров рекурсий передаем следующие переменные:

  • [math]node[/math] — номер (в массиве с деревом отрезков) текущей вершины дерева.
  • [math]a[/math], [math]b[/math] — левая и правая границы запрашиваемого полуинтервала.

Пусть [math]l[/math], [math]r[/math] — это левая и правая границы полуинтервала, за которые "отвечает" наша вершина. Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).

Для текущего состояния проверяем следующие условия:

  • Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
Например: текущий [math][1 \ldots 3)[/math], а искомый [math][3 \ldots 5)[/math];
  • Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
Например: текущий [math][2 \ldots 3)[/math], а искомый [math][2 \ldots 4)[/math];
  • Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.

Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней [math]\log n[/math], то операция выполняется за [math]O(\log n)[/math].

Пример

Рассмотрим данный алгоритм на примере задачи [math]\mathrm{RSQ}[/math] (Range Sum Query — запрос суммы на отрезке).

При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.

Пусть дерево содержит [math]8[/math] листьев и запрашиваемая сумма — это отрезок [math][1 \ldots 4][/math] (полуинтервал [math][1 \ldots 5)[/math]).

Пример рабoты алгоритма

Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):

  • На глубине [math]0[/math].
    • Текущий полуинтервал [math][0 \ldots 8)[/math] пересекается с [math][1 \ldots 5) \Rightarrow[/math] рекурсивно переходим к [math][0 \ldots 4)[/math] и [math][4 \ldots 8)[/math]


  • На глубине [math]1[/math].
    • [math][0 \ldots 4)[/math] и [math][4 \ldots 8)[/math] пересекаются с [math] [1 \ldots 5) \Rightarrow [/math] переходим по рекурсивным вызовам на полуинтервалах [math][0 \ldots 2)[/math], [math][2 \ldots 4)[/math], [math][4 \ldots 6)[/math] и [math][6 \ldots 8)[/math]


  • На глубине [math]2[/math].
    • [math][0 \ldots 2)[/math] и [math][4 \ldots 6)[/math] пересекаются с [math][1 \ldots 5) \Rightarrow [/math] переходим в листья [math][0 \ldots 1), [1 \ldots 2), [4 \ldots 5), [5 \ldots 6) [/math]
    • [math][2 \ldots 4) [/math] полностью лежит внутри [math][1 \ldots 5) \Rightarrow [/math] возвращаем сумму на этом отрезке
    • [math][6 \ldots 8)[/math] не пересекается с [math][1 \ldots 5) \Rightarrow [/math] возвращаем нулевое значение


  • На глубине [math]3[/math].
    • Листья [math][1 \ldots 2), [4 \ldots 5)[/math] лежат в запрашиваемом интервале [math]\Rightarrow [/math] возвращаем значения в них
    • Листья [math][0 \ldots 1), [5 \ldots 6)[/math] лежат вне [math][1 \ldots 5) \Rightarrow [/math] возвращаем нейтральное значение

Таким образом ответ на полуинтервале [math][1 \ldots 5)[/math] равен сумме значений в вершинах, отвечающих за полуинтервалы [math][1 \ldots 2)[/math], [math][2 \ldots 4)[/math] и [math][4 \ldots 5)[/math].

Реализация

Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.

Пусть в узлах дерева хранятся структуры из трех полей:

  • [math]\mathtt{left}[/math] — левая граница полуинтервала, за который "отвечает" текущая вершина.
  • [math]\mathtt{right}[/math] — правая граница этого полуинтервала.
  • [math] \mathtt{res}[/math] — результат операции на полуинтервале.
 int query(int node, int a, int b)     
     l = tree[node].left
     r = tree[node].right 
     if [l, r) [math]\cap [/math] [a, b) == [math]\varnothing[/math]
         return [math]\varepsilon[/math]                    // [math]\varepsilon[/math] — нейтральный для данной операции элемент
     if [l, r) [math]\subset[/math] [a, b)
         return tree[node].res
     return query(node * 2 + 1, a, b) [math] \circ [/math] query(node * 2 + 2, a, b)

См. также

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