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

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

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

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

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

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

1. $a \odot (b \odot c) = (a \odot b) \odot c$
2. $(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)$

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

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

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

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

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

push

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

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

update

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

void update(int node, int a, int b, T val) {
    // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса 
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r) $\cap$ [a, b) == $\varnothing$
           return;
       if [l, r) $\subset$ [a, b)
           tree[node].d = tree[node].d $\odot$ 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 $\odot$ tree[2 * node + 1].d) $\oplus$ 
                         (tree[2 * node + 2].ans $\odot$ tree[2 * node + 2].d);
}

query

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

T query(int node, int a, int b) {
       l = tree[node].left;
       r = tree[node].right; 
       if  [l, r ) $\cap$ [a, b) == $\varnothing$
           return $\perp$;
       if [l, r) $\subset$ [a, b)
           return tree[node].ans $\odot$ tree[node].d;
       push(node);   
       T ans = query(node * 2 + 1, a, b) $\oplus$  
                query(node * 2 + 2, a, b));
       tree[node].ans = (tree[2 * node + 1].ans $\odot$ tree[2 * node + 1].d) $\oplus$ 
                         (tree[2 * node + 2].ans $\odot$ tree[2 * node + 2].d);
       return ans;
}

См. также

• Дерево отрезков. Построение

• Реализация запроса в дереве отрезков сверху

• Реализация запроса в дереве отрезков снизу

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

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

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