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

Дерево отрезков позволяет осуществлять так называемые массовые операции, то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно [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]
3. [math]c \odot (a \oplus b) = (c \odot a) \oplus (c \odot b)[/math]

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

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

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

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

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

• [math]left[/math] — левая граница полуинтервала, за который "отвечает" текущая вершина.
• [math]right[/math] — правая граница этого полуинтервала.
• [math] ans[/math] — сумма на отрезке по операции [math]\oplus[/math].
• [math] 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, my_type val) {
   // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r) [math]\bigcap [/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);
}

get_ans

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

my_type get_ans(int node, int a, int b) {
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r )[math]\bigcap [/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);   
       int ans = get_ans (node * 2 + 1, a, b) [math]\oplus[/math]  
                get_ans (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;
}

Псевдокод в общем виде

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

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

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

   // Процедура "проталкивания" несогласованности детям
void push(int 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]; // Нейтральный элемент
} 
   // Процедура ответа на множественные запросы.  
void update(int node, int a, int b, my_type val) {
   // val - значение, которое поступило в качестве параметра на запрос
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r) [math]\bigcap [/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);
}
   // Функция ответа на запросы
my_type get_ans(int node, int a, int b) {
   // node - текущая вершина, a и b - границы запроса
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r )[math]\bigcap [/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);   
       int ans = get_ans (node * 2 + 1, a, b) [math]\oplus[/math]  
                get_ans (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;
}

Ссылки

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

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