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

Дерево отрезков позволяет осуществлять так называемые массовые операций, то есть данная структура позволяет выполнять операций с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно [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]O(N)[/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 = ans;
    // Пересчитываем свое значение
       tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d, 
                         tree[2 * node + 2].min + tree[2 * node + 2].d); 
}
 
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);
}

Ссылки

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

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