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

Дерево отрезков позволяет отвечать на запросы к целым отрезкам подряд идущих элементов, причем за то же время [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]\odot[/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 :: Дерево отрезков

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