Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>. ==Несогласованные поддеревья==Сперва рассмотрим так называемые '''несогласованные поддеревья'''. Пусть дерево отрезков хранит в вершинах результат выполнения операции <tex>\oplus</tex> на текущем отрезке, а запрос обновления идет по операции <tex>\odot</tex>. В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации вторая операция должна быть ассоциативной, и должен выполняться распределительный закон с <tex>\oplusodot</tex>должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:

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

Пусть дерево отрезков храниться в массиве Для эффективной реализации будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>T\odot</tex>для всех элементов текущего отрезка. Для реализации Тем самым мы сможем обрабатывать запрос массового обновления будем хранить дополнительный массив несогласованностей на любом подотрезке эффективно, вместо того чтобы изменять все <tex>dO(N)</tex>значений. Истинные значения Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>T'[v] = T[v] + d[v]\oplus</tex>, так как значение в детях могло измениться.

Нумерация массива с нуля=== push ==="Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, то есть корень дерева {чтобы в детях в момент обработки были корректные данные. '''void''' push(int node) { <font color=green>// node ---}} Tтекущая вершина </font> tree[2 * node + 1].d = tree[2 * node + 1].d <tex>\odot</tex> tree[node].d; tree[2 * node + 2].d = tree[2 * node + 2].d <tex>\odot</tex> tree[node].d; tree[0node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент </font> }

=== update ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции <tex>\oplus</tex> на текущем отрезке.   get_min'''void''' update(vint node, lint a, int b, rT val) { <font color=green> // v val - текущая вершиназначение, l которое поступило в качестве параметра на запрос, a и r b - границы запроса</font> l = tree[node].left; r = tree[node].right; '''if (отрезок соответствующий v не пересекается с ''' [l, r])<tex>\cap </tex> [a, b) == <tex> \varnothing</tex> '''return inf // бесконечность - нейтральный элемент относительно min'''; '''if (отрезок соответствующий v содержится в ''' [l, r]) <tex>\subset </tex> [a, b) return tree[vnode] + .d= tree[vnode].d <tex>\odot</tex> val; // Раздаем детям '''return'''; d[2 * v + 1] = d[2 * v + 1] + d[v] d[2 * v + 2] = d[2 * v + 2] + d[v] push(node); d[v] <font color= 0 green>// Вызываем функцию от Обновление детей</font> ans = min(get_min update(2 * v node + 1, la, b, rval), get_min; update(2 * v node + 2, la, b, r)val); <font color=green>// Пересчитываем свое значениеПересчет значения на текущем отрезке </font> T tree[vnode] .ans = min(Ttree[2 * v node + 1] + d.ans <tex>\odot</tex> tree[2 * v node + 1], T.d) <tex>\oplus</tex> (tree[2 * v node + 2] + d.ans <tex>\odot</tex> tree[2 * v node + 2].d) return ans;

=== query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  update'''T''' query(vint node, l, rint a, xint b) { // x - сколько нужно прибавить на отрезке l = tree[node].left; r = tree[node].right; '''if (отрезок соответственный v не пересекается с ''' [l, r])<tex>\cap</tex> [a, b) == <tex> \varnothing</tex> '''return''' <tex>\perp</tex>; '''if (отрезок соответственный v содержится в ''' [l, r]) { d<tex>\subset</tex> [v] = d[v] + xa, b) '''return } // Раздаем детям d''' tree[2 * v + 1node] = d.ans <tex>\odot</tex> tree[2 * v + 1node] + .d[v]; d[2 * v + 2] = d[2 * v + 2] + d[v] push(node); d[v] T ans = 0 // Вызываем функцию от детей updatequery(node * 2 * v + 1, la, r, xb)<tex>\oplus</tex> update query(node * 2 * v + 2, la, r, xb)); // Пересчитываем свое значение T tree[vnode] .ans = min(Ttree[2 * v node + 1] + d.ans <tex>\odot</tex> tree[2 * v node + 1], T.d) <tex>\oplus</tex> (tree[2 * v node + 2] + d.ans <tex>\odot</tex> tree[2 * v node + 2].d); '''return''' ans;