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

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

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

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

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

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] значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается так называемым "проталкиванием" несогласованности детям при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операций [math]\oplus[/math], так как значение в детях могло измениться.

Таким образом необходимо во-первых не забыть раздать детям несогласованность, во-вторых вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.

Пример

Рассмотрим массовые операции на отрезке на примере задачи "Прибавление на отрезке". При этом мы должны отвечать на запрос минимума на отрезке.

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

Ниже приведен код данного алгоритма.

Псевдокод

Используется классическая реализация дерева отрезка с полуинтервалами.

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

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

   // Процедура "проталкивания" несогласованности детям
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;
       r = tree[node].right; 
       if  [l, r)[math]\bigcap [/math][a, b) == [math] \varnothing[/math]
           return [math]\infty[/math];
       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;
       r = tree[node].right; 
       if  [l, r)[math]\bigcap [/math][a, b) == [math] \varnothing[/math]
           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);
}

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

Пусть поступают запросы двух типов — поиск элемента, соответствующего операций [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[node].d;
       tree[2 * node + 2].d += tree[node].d;
       tree[node].d = 0;
} 
   // Процедура ответа на множественные запросы.  
void update(int node, int a, int b, int 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) == [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);
}
   // Функция ответа на запросы
int get(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]\infty[/math];
       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;
}

Ссылки

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

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