Задача нахождения суммы элементов массива на интервале, методы её решения

Определение

Часто возникает задача, когда нужно посчитать сумму от i-го до j-го элемента в массиве A.
Формально определим её:
Найти sum =
Рассмотрим как такую задачу решают простым методом.

Методы решения

1. Можно каждый раз суммировать элементы с i-го по j-тый
   Эффективность такого метода:
   Обновление массива: O(1)
   Вычисление суммы: O(n)
2. Можно завести дополнительный массив частичных сумм P, где P[1] = A[1], P[i] = P[i-1] + A[i], i>1
   И тогда сумма равна:
   Sum =
| P[j] – P[i-1] , i>1
| P[j], i=1
   Эффективность такого метода:
   Обновление массива: O(n)
   Вычисление суммы: O(1)
3. Оказывается можно объединить эти два метода и получить решение, которое способно обновлять массив и вычислять сумму более эффективно
   Этот метод использует дерево Фенвика.
   Дерево Фенвика — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.
   Нужно хранить частичные суммы в исходном массиве не от начала до i-го, а от такого элемента, номер которого вычисляется по формуле: i-f(i)+1.
   То есть P[i] = ? A[j], j € (i-f(i);i], где f(i) – максимальная степень двойки, на которую делится i.
   Нетрудно убедиться, что f(i)=i?(i & (i?1)).
   Пусть n — длина массива A.
   Выберем такое минимальное k, что 2^k >=n.
   Тогда для хранения дерева Фенвика понадобится массив P из 2^k элементов. Будем нумеровать их от 1 до 2k.
   В ячейке P[i] будет храниться сумма в ячейках массива A с i - f(i) + 1 по i.

Исходный код для вычисления суммы с 1 по k

for(int i=k;i>0;i-=i&-i)
Sum+=P[i];

Исходный код для увеличения значения t-й ячейки массива A на число x:

for(int i=t;i<=n;i+=i&-i)
P[i]+=x;
В приведенном коде i&-i и есть то вычисление следующего f(i).
В итоге искомая сумма будет равна:
Sum =
| P[j] – P[i-1] , i>1
| P[j], i=1

Эффективность такого метода:
Обновление массива: O(log(n))
Вычисление суммы: O(log(n))