146
правок
Изменения
Нет описания правки
'''while''' i < N
t[i] += d
i = i | (i + 1);
Часто можно встретить задачу, где требуется заменить значение элемента <tex>a_i</tex> на <tex>x</tex>. Заметим, что если вычислить разность <tex>x</tex> и <tex>a_{i}</tex>, то можно свести эту задачу к операции прибавления <tex>d</tex> к <tex>a_i</tex>.
Обозначим <tex> G_i = \mathrm sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> \mathrm sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
Для нахождения <tex>sum(i)</tex> будем действовать следующим образом. Берём <tex>T_i</tex>, которое является суммой элементов с индексами от <tex>F(i)</tex> до <tex>i</tex>. Теперь к этому значению нужно прибавить <tex>sum(F(i) - 1)</tex>. Рекурсивно Аналогично продолжаем складывать, пока не <tex>F(j)</tex> не станет равным <tex>0</tex>.
=== Реализация ===
Приведем код функции <tex> \mathrm sum(i) </tex>:
'''int''' sum(i):
result = t[i]0; '''ifwhile''' f(i) > = 0 result += sum(t[i] i = f(i) - 1) '''else''' '''return''' result
==Сравнение дерева Фенвика и дерева отрезков==
