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

Дерево отрезков позволяет осуществлять так называемые массовые операций, то есть данная структура позволяет выполнять операций с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно [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 для прибавления). Для реализации вторая операция должна быть ассоциативной, и операций должны удовлетворять свойству дистрибутивности:

Если операция [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 :: Дерево отрезков

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

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