Изменения

Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.

Напишем функцию, которая будет прибавлять к элементу <tex>a_i</tex> число <tex>d</tex>, и при этом меняет соответствующие частичные суммы. Так как наш массив содержит <tex>N</tex> элементов, то мы будем искать <tex>i_{next}</tex> до тех пор, пока оно не превышает значение <tex>N</tex>.

'''while''' i < N

t[i] += d

Часто можно встретить задачу, где требуется заменить значение элемента <tex>a_i</tex> на <tex>x</tex>. Заметим, что если вычислить разность <tex>x</tex> и <tex>a_{i}</tex>, то можно свести эту задачу к операции прибавления <tex>d</tex> к <tex>a_i</tex>.