== Несогласованные поддеревья ==
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции <tex>\oplus</tex>). При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Для того чтобы узнать истинное значение нужно «собрать» все несогласованности на пути от вершины к корню дерева: <tex>b_i = b'_i \odot \left(\bigodot\limits_k d_k \right)</tex>. То есть для этого необходимо, чтобы вторая операция <tex>\odot</tex> была ассоциативной. Если в вершине хранится истинное значение суммы, то<tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex>. Если операция <tex>\odot</tex> не коммутативна, то нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.
== Массовые операции ==на отрезке рассмотрим на примере минимума на отрезке и прибавления на отрезке.
Рассмотрим два примера: присваивание на отрезкеПусть дерево отрезков храниться в массиве T. Для реализации массового обновления будем хранить дополнительный массив несогласованностей d[]. Истинные значения <tex>T'[v] = T[v] + d[v]</tex>.
=== Прибавление === Чтобы делать запрос прибавления эффективноПсевдокод (нумерация массивов с нуля, будем хранить в каждой вершине то есть корень дерева отрезков дополнительное значение {{---}} сколько надо прибавить ко всем числам этого отрезка целиком. Например, если приходит запрос "прибавить ко всему массиву <tex>aT[0 \ldots n-1]</tex> число 2", то мы поставим в корне дерева число 2. Тем самым мы сможем обрабатывать запрос прибавления на любом подотрезке эффективно, вместо того чтобы изменять все O(n) значений. Псевдокод: getget_min(v, l, r, d) // v - текущая вершина, l и r - границы запроса if (отрезок соответственный v не пересекается с [l, d r]) return inf // бесконечность - несогласованностьнейтральный элемент относительно min Если if (отрезок соответственный v входит содержится в [l, r], то) return tree[v] + d[v] d[2*v+1] = d[2*v+1] + d[v] d[2*v+2] =d[2*v+2] + d[v] d[v] =0 ans = Присваивание min(get_min(2*v+1, l, r), get_min(2*v+2, l, r)) T[v] === <tex>amin(T[2*v+1]+d[2*v+1],T[i2*v+2]..a+d[j2*v+2] \leftarrow c</tex>) return ansДля того update(v, l, r, чтобы присвоить всем элементам x) // x - сколько нужно прибавить на отрезке новое значение if (отрезок соответственный v не пересекается с [l, нужно этот r]) return if (отрезок разбить, как соответственный v содержится в обычном запросе[l, на <tex>\operatorname r]) {log d[v] = d[v] + x return }n</tex> отрезков d[2*v+1] = d[2*v+1] + d[v] d[2*v+2] = d[2*v+2] + d[v] d[v] = 0 update(2*v+1, l, r, x) update(2*v+2, l, r, x) T[v] = min(T[2*v+1]+d[2*v+1], и в соответствующие узлы добавить несогласованность: <tex>d_k \leftarrow d_k \odot c</tex>.T[2*v+2]+d[2*v+2]) return ans
