Занятие 7

Если нужно находить суммы в часто изменяемом массиве, то можно использовать дерево частичных сумм, которое строится следующим образом. Для каждой пары элементов вычисляем их сумму и помещаем результат в массив более высокого уровня, аналогично поступаем для получившегося массива, пока не получим единственное значение. Желательно, чтобы размер массива был степенью 2, для этого можно дополнить массив нулями.

          57
        /    \
     49       8
    /  \     /  \
  20    29  8    0
 / \   / \ / \  / \
13 7  25 4 8 -  - -

Время изменения такого дерева `O(log_2\ N)`, а время вычисления суммы `O(log_2\ N)`.