Несогласованные поддеревья. Реализация массового обновления — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 8 участников)
Строка 1: Строка 1:
Дерево отрезков позволяет осуществлять так называемые '''массовые операций''', то есть данная структура позволяет выполнять операций с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>.
+
[[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>.
  
 
==Несогласованные поддеревья==
 
==Несогласованные поддеревья==
 
Сперва рассмотрим так называемые '''несогласованные поддеревья'''.
 
Сперва рассмотрим так называемые '''несогласованные поддеревья'''.
  
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации вторая операция должна быть ассоциативной, и операций должны удовлетворять свойству дистрибутивности:
+
Пусть дерево отрезков хранит в вершинах результат выполнения операции <tex>\oplus</tex> на текущем отрезке, а запрос обновления идет по операции <tex>\odot</tex>.
 +
 
 +
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации операция <tex>\odot</tex> должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:
  
 
#<tex>a \odot (b \odot c) = (a \odot b) \odot c</tex>
 
#<tex>a \odot (b \odot c) = (a \odot b) \odot c</tex>
 
#<tex>(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)</tex>
 
#<tex>(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)</tex>
#<tex>c \odot (a \oplus b) = (c \odot a) \oplus (c \odot b)</tex>
 
  
 
==Массовое обновление==
 
==Массовое обновление==
  
Рассмотрим в общем виде реализацию массовой операций на отрезке. Пусть необходимо отвечать запросы относительно операций <tex>\oplus</tex>, а запрос массового обновления идет по операций <tex>\odot</tex>.
+
Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</tex>.
  
Для эффективной реализаций будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операций <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается так называемым "проталкиванием" несогласованности детям при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операций <tex>\oplus</tex>, так как значение в детях могло измениться.
+
Для эффективной реализации будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться.
  
Таким образом необходимо во-первых не забыть раздать детям несогласованность, во-вторых вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.
+
Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:
 +
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
 +
* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.
 +
* <tex>\mathtt{ ans}</tex> {{---}} результат на отрезке по операции <tex>\oplus</tex>.
 +
* <tex>\mathtt{ d}</tex> {{---}} несогласованность.
  
==Пример==
+
=== push ===
 
+
"Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные.
Рассмотрим массовые операции на отрезке на примере задачи "Прибавление на отрезке". При этом мы должны отвечать на запрос минимума на отрезке.
+
 
+
'''void''' push(int node) {                                               <font color=green>// node - текущая вершина </font>
Следуя вышеописанному алгоритму будем в каждой вершине хранить минимум на текущем отрезке и несогласованность {{---}} сколько необходимо прибавить ко всем числам этого отрезка(соответственно при запросе минимума истинный минимум на отрезке при корректной несогласованности {{---}} сумма несогласованности и значения в вершине). При этом не забудем выполнять "проталкивание" несогласованности и делать обновление минимума на текущем отрезке.  
+
        tree[2 * node + 1].d = tree[2 * node + 1].d <tex>\odot</tex> tree[node].d;
 
+
        tree[2 * node + 2].d = tree[2 * node + 2].d <tex>\odot</tex> tree[node].d;
Ниже приведен код данного алгоритма.
+
        tree[node].d = <tex>\perp</tex>;                                          <font color=green> // Нейтральный элемент </font>
 
+
}
==Псевдокод==
 
Используется классическая реализация дерева отрезка с полуинтервалами.
 
  
Пусть в узлах дерева хранятся структуры из четырех полей:
+
=== update ===
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
+
Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции <tex>\oplus</tex> на текущем отрезке.  
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
 
* <tex> min</tex> {{---}} минимум на полуинтервале.
 
* <tex> d</tex> {{---}} несогласованность.
 
  
    // Процедура "проталкивания" несогласованности детям
+
  '''void''' update(int node, int a, int b, T val) {
  void push(int node) {
+
     <font color=green> // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса </font>
        tree[2 * node + 1].d += tree[node].d;
 
        tree[2 * node + 2].d += tree[node].d;
 
        tree[node].d = 0;
 
}
 
 
int get_min(int node, int a, int b) {
 
     // node - текущая вершина, a и b - границы запроса
 
        l = tree[node].left;
 
        r = tree[node].right;
 
        if  [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>
 
            return <tex>\infty</tex>;
 
        if [l, r) == [a, b)
 
            return tree[node].min + tree[node].d;
 
        push(node); 
 
        int m = (l + r) / 2;
 
        int ans = min(get_min (node * 2 + 1, a, min(b, m)),
 
                get_min (node * 2 + 2, max(a, m), b)));
 
    // Пересчитываем свое значение
 
        tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d,
 
                          tree[2 * node + 2].min + tree[2 * node + 2].d);
 
        return ans;
 
}
 
 
 
void update(int node, int a, int b, int val) {
 
    // val - значение, на которое нужно увеличить отрезок
 
 
         l = tree[node].left;
 
         l = tree[node].left;
 
         r = tree[node].right;  
 
         r = tree[node].right;  
         if  [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>
+
         '''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex>
             return;
+
             '''return''';
         if [l, r) == [a, b)
+
         '''if''' [l, r) <tex>\subset </tex> [a, b)
             tree[node].d += val;
+
             tree[node].d = tree[node].d <tex>\odot</tex> val;
             return;
+
             '''return''';
 
   
 
   
 
         push(node);  
 
         push(node);  
     // Вызываем обновление детей
+
     <font color=green>// Обновление детей </font>
 
         update(2 * node + 1, a, b, val);
 
         update(2 * node + 1, a, b, val);
 
         update(2 * node + 2, a, b, val);
 
         update(2 * node + 2, a, b, val);
         tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d,
+
    <font color=green>// Пересчет значения на текущем отрезке </font>
                           tree[2 * node + 2].min + tree[2 * node + 2].d);
+
         tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex>
 +
                           (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d);
 
  }
 
  }
  
==Псевдокод в общем виде==
+
=== query ===
Используется классическая реализация дерева отрезка с полуинтервалами.
+
Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).
 
 
Пусть в узлах дерева хранятся структуры из четырех полей:
 
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
 
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
 
* <tex> min</tex> {{---}} минимум на полуинтервале.
 
* <tex> d</tex> {{---}} несогласованность.
 
  
    // Процедура "проталкивания" несогласованности детям
+
  '''T''' query(int node, int a, int b) {
  void push(int node) {
 
        tree[2 * node + 1].d += tree[node].d;
 
        tree[2 * node + 2].d += tree[node].d;
 
        tree[node].d = 0;
 
}
 
 
int get_min(int node, int a, int b) {
 
    // node - текущая вершина, a и b - границы запроса
 
 
         l = tree[node].left;
 
         l = tree[node].left;
 
         r = tree[node].right;  
 
         r = tree[node].right;  
         if  [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>
+
         '''if''' [l, r ) <tex>\cap</tex> [a, b) == <tex> \varnothing</tex>
             return <tex>\infty</tex>;
+
             '''return''' <tex>\perp</tex>;
         if [l, r) == [a, b)
+
         '''if''' [l, r) <tex>\subset</tex> [a, b)
             return tree[node].min + tree[node].d;
+
             '''return''' tree[node].ans <tex>\odot</tex> tree[node].d;
 
         push(node);   
 
         push(node);   
         int m = (l + r) / 2;
+
         T ans = query(node * 2 + 1, a, b) <tex>\oplus</tex> 
        int ans = min(get_min (node * 2 + 1, a, min(b, m)),
+
                 query(node * 2 + 2, a, b));
                 get_min (node * 2 + 2, max(a, m), b)));
+
         tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex>
    // Пересчитываем свое значение
+
                           (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d);
         tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d,
+
         '''return''' ans;
                           tree[2 * node + 2].min + tree[2 * node + 2].d);
 
        return ans;
 
}
 
 
 
void update(int node, int a, int b, int val) {
 
    // val - значение, на которое нужно увеличить отрезок
 
        l = tree[node].left;
 
        r = tree[node].right;
 
        if  [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>
 
            return;
 
        if [l, r) == [a, b)
 
            tree[node].d += val;
 
            return;
 
 
        push(node);
 
    // Вызываем обновление детей
 
        update(2 * node + 1, a, b, val);
 
        update(2 * node + 2, a, b, val);
 
         tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d,
 
                          tree[2 * node + 2].min + tree[2 * node + 2].d);
 
 
  }
 
  }
  
==Ссылки==
+
==См. также==
 +
*[[Дерево отрезков. Построение]]
 +
 
 +
* [[Реализация запроса в дереве отрезков сверху]]
 +
 
 +
*[[Реализация запроса в дереве отрезков снизу]]
 +
 
 +
==Источники информации==
  
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
+
* [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://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  Дерево отрезков — Википедия]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]

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

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

Несогласованные поддеревья

Сперва рассмотрим так называемые несогласованные поддеревья.

Пусть дерево отрезков хранит в вершинах результат выполнения операции [math]\oplus[/math] на текущем отрезке, а запрос обновления идет по операции [math]\odot[/math].

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции [math]\oplus[/math]) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок [math]a_i..a_j[/math] хранится несогласованность [math]d[/math]. Если в вершине хранится истинное значение суммы, то [math]d = \perp[/math] — нейтральный элемент относительно операции [math]\odot[/math] (например 0 для прибавления). Для реализации операция [math]\odot[/math] должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:

  1. [math]a \odot (b \odot c) = (a \odot b) \odot c[/math]
  2. [math](a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)[/math]

Массовое обновление

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

Для эффективной реализации будем использовать описанную выше структуру — несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции [math]\oplus[/math], храним несогласованность — величина, с которой нужно выполнить операцию [math]\odot[/math] для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все [math]O(N)[/math] значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции [math]\oplus[/math], так как значение в детях могло измениться.

Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:

  • [math]\mathtt{left}[/math] — левая граница полуинтервала, за который "отвечает" текущая вершина.
  • [math]\mathtt{right}[/math] — правая граница этого полуинтервала.
  • [math]\mathtt{ ans}[/math] — результат на отрезке по операции [math]\oplus[/math].
  • [math]\mathtt{ d}[/math] — несогласованность.

push

"Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные.

void push(int node) {                                               // node - текущая вершина 
       tree[2 * node + 1].d = tree[2 * node + 1].d [math]\odot[/math] tree[node].d;
       tree[2 * node + 2].d = tree[2 * node + 2].d [math]\odot[/math] tree[node].d;
       tree[node].d = [math]\perp[/math];                                           // Нейтральный элемент 
}

update

Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции [math]\oplus[/math] на текущем отрезке.

void update(int node, int a, int b, T val) {
    // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса 
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r) [math]\cap [/math] [a, b) == [math] \varnothing[/math]
           return;
       if [l, r) [math]\subset [/math] [a, b)
           tree[node].d = tree[node].d [math]\odot[/math] val;
           return;

       push(node); 
   // Обновление детей 
       update(2 * node + 1, a, b, val);
       update(2 * node + 2, a, b, val);
    // Пересчет значения на текущем отрезке 
       tree[node].ans = (tree[2 * node + 1].ans [math]\odot[/math] tree[2 * node + 1].d) [math]\oplus[/math] 
                         (tree[2 * node + 2].ans [math]\odot[/math] tree[2 * node + 2].d);
}

query

Получение ответа по операции [math]\oplus[/math]. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции [math]\oplus[/math] с текущим ответом истинное значение на отрезке (то есть результат сложения по операции [math]\odot[/math] значения в вершине с несогласованностью).

T 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]\perp[/math];
       if [l, r) [math]\subset[/math] [a, b)
           return tree[node].ans [math]\odot[/math] tree[node].d;
       push(node);   
       T ans = query(node * 2 + 1, a, b) [math]\oplus[/math]  
                query(node * 2 + 2, a, b));
       tree[node].ans = (tree[2 * node + 1].ans [math]\odot[/math] tree[2 * node + 1].d) [math]\oplus[/math] 
                         (tree[2 * node + 2].ans [math]\odot[/math] tree[2 * node + 2].d);
       return ans;
}

См. также

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