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

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

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции [math]\oplus[/math]). При этом в корне поддерева, которому соответствует отрезок [math]a_i..a_j[/math] хранится несогласованность [math]d[/math]. Для того чтобы узнать истинное значение нужно «собрать» все несогласованности на пути от вершины к корню дерева: [math]b_i = b'_i \odot \left(\bigodot\limits_k d_k \right)[/math]. То есть для этого необходимо, чтобы вторая операция [math]\odot[/math] была ассоциативной. Если в вершине хранится истинное значение суммы, то [math]d = \perp[/math] — нейтральный элемент относительно операции [math]\odot[/math].

Массовые операции

Рассмотрим два примера: прибавление и присваивание на отрезке

Прибавление

Чтобы делать запрос прибавления эффективно, будем хранить в каждой вершине дерева отрезков дополнительное значение — сколько надо прибавить ко всем числам этого отрезка целиком. Например, если приходит запрос "прибавить ко всему массиву [math]a[0 \ldots n-1][/math] число 2", то мы поставим в корне дерева число 2. Тем самым мы сможем обрабатывать запрос прибавления на любом подотрезке эффективно, вместо того чтобы изменять все O(n) значений.

Псевдокод:

get(v, L, R, l, r, d)

// v - текущая вершина, L и R - отрезок, соответственный текущей вершине, l и r - границы запроса, d - несогласованность

Присваивание

[math]a[i]..a[j] \leftarrow c[/math]

Для того, чтобы присвоить всем элементам на отрезке новое значение, нужно этот отрезок разбить, как в обычном запросе, на [math]\operatorname {log}n[/math] отрезков, и в соответствующие узлы добавить несогласованность: [math]d_k \leftarrow d_k \odot c[/math].