Изменения

Рассмотрим два примера: прибавление и присваивание на отрезке и прибавление  === Прибавление === Чтобы делать запрос прибавления эффективно, будем хранить в каждой вершине дерева отрезков дополнительное значение {{---}} сколько надо прибавить ко всем числам этого отрезка целиком. Например, если приходит запрос "прибавить ко всему массиву <tex>a[0 \ldots n-1]</tex> число 2", то мы поставим в корне дерева число 2. Тем самым мы сможем обрабатывать запрос прибавления на отрезкелюбом подотрезке эффективно, вместо того чтобы изменять все O(n) значений. Псевдокод:: get(v, L, R, l, r, d):// v - текущая вершина, L и R - отрезок, соответственный текущей вершине, l и r - границы запроса, d - несогласованность