146
правок
Изменения
Нет описания правки
modify(i, d)
Построение дерева можно осуществить, исходя из его описания. Но можно быстрее, если использовать функцию <tex>\mathrm {modify}</tex> для каждого элемента массива <tex>A</tex>. Тогда мы получим время работы <tex>O(n \log {n})</tex>.
'''function''' build():
В качестве бинарной операции <tex> \circ </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>\mathrm {sum(i)}</tex> будем действовать следующим образом. Берём <tex>T_i</tex>, которое является суммой элементов с индексами от <tex>F(i)</tex> до <tex>i</tex>. Теперь к этому значению нужно прибавить <tex>\mathrm {sum(F(i) - 1)}</tex>. Аналогично продолжаем складывать, пока не <tex>F(j)</tex> не станет равным <tex>0</tex>.
Покажем, что запрос суммы работает за <tex>O(\log{n})</tex>. Рассмотрим двоичную запись числа <tex>i</tex>. Функция <tex>F(i)</tex> заменила его последние единицы на нули (заметим, что количество нулей в конце станет больше, чем количество единиц в конце до этого). Теперь вычтем единицу из <tex>F(i)</tex> (переход к следующему столбику). Количество единиц в конце увеличилось, по сравнению с <tex>i</tex>, так как мы заменили все нули в конце на единицы. Проводя эти действия дальше, мы придём к тому, что получили <tex>0</tex>. В худшем случае мы должны были повторять эти операции <tex>l</tex> раз, где <tex>l</tex> — количество цифр в двоичной записи числа <tex>i</tex>, что не превосходит <tex>\log_{2}{i} + 1</tex>. Значит, запрос суммы выполняется за <tex>O(\log{n})</tex>.
=== Реализация ===
Приведем код функции <tex> \mathrm {sum(i) } </tex>:
'''int''' sum(i):
result = 0
