Дерево отрезков

и позволяющая эффективно (за O(log(n))) выполнять следующие операции:
изменять значение любого элемента в массиве или элементов на отрезке [i,j];
выполнять некоторую операцию на отрезке [i,j] (сумма, максимумб минимум и др.).

7

8

3

9

10

4

11

12

5

13

14

6

1

2

0

или вычислять функцию на отрезке массива.
Строится бинарное дерево, в листьях которого содержаться значения элементов массива, а во всех остальных вершинах – функция, вычисленная на основании значений в детях этой вершины, что позволит экономить время при вычислении функции на отрезке.
Тогда при изменении элемента требуется пересчитывать значения во всех вершинах от одного из листов до корня.
Пример ДО для суммы:

1

2

3

3

0

3

2

-1

1

4

3

7

6

8

14

соответствует индекс 0, его левому ребёнку индекс 1, а правому – 2. Тогда левый ребёнок вершины 1 – 3, а правый – 4. Т.е. для вершины с индексом i левым ребёнком будет вершина с индексом i*2+1, а для правой – i*2+2.
Пусть размер исходного массива равен n. Тогда в корне будет храниться значение функции на отрезке [0; n-1], в первой вершине – на отрезке [0, (n-1)/2], во второй – на отрезке [(n-1)/2 + 1; n-1] и т.д.
Тогда все операции над деревом отрезков можно определить как рекурсивные функции обхода по дереву, запускаемые из корня (вершины 0) с поддержкой того, что в текущей вершине рассматривается значение функции на отрезке [tl; tr], где: - для нулевой вершины tl = 0, tr = 1; - для левого ребёнка tl’ = tl, tr’ =(tl + tr) / 2; - для правого tl’ = (tl + tr) / 2 + 1, tr’ = tr.

для него нужно поддерживать операции присвоения на отрезке и получения значения элемента по индексу.
В листьях дерева по прежнему будем хранить значения элементов массива, а в остальных изначально UNDEF.
Во время операции присвоения, если отрезок, за который отвечает текущая вершина, целиком покрывается отрезком, на котором происходит присвоение, запомним в этой вершине присваиваемое число и не будем выполнять операцию присвоения у детей.
Значения в листьях после таких операций присвоения могут оказаться неактуальными. Для исправления этого при рассмотрении вершины во время обхода необходимо «протолкнуть» значение из текущей вершины вниз, то есть если в вершине было значение не UNDEF, то присвоить это значение её детям, а самой вершине присвоить UNDEF.