Изменения
Нет описания правки
{| border="1"
|<tex>i_{prev}</tex>
|<tex>\cdots 011 \cdots 1)</tex>
|-
|<tex>i_{prev} + 1</tex>
|<tex>\cdots 100 \cdots 0)</tex>
|-
|<tex>i_{next}</tex>
|<tex>\cdots 111 \cdots 1)</tex>
|}
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.
Напишем функцию, которая будет изменять <tex>a_i</tex> элемент на <tex>d</tex>, и при этом меняет соответствующие частичные суммы.
int modify(int i, int d)
{
while (i < N)
{
t[i] += d;
i = i | (i + 1);
}
}
== Запрос получения суммы на префиксе ==
