Изменения

|proof=Из доказанной выше леммы следует, что первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) \leqslant i </tex>. По формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как <tex>F(i)</tex> осталось прежним или уменьшилось, а <tex> i </tex> увеличилось. <tex> F(i) </tex> не может увеличитсяувеличиться, так как функция <tex> F </tex> заменяет последние подряд идущие единицы числа <tex> i </tex> на нули, а по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> у нового значения <tex> i </tex> увеличивается количество единиц в конце, что не может привести к увеличению <tex> F(i) </tex>. Докажем от противного, что нельзя рассматривать значения <tex> i </tex>, отличные от тех, которые мы получили по формуле. Рассмотрим две различные последовательности индексов. Первая последовательность получена по формуле, вторая — некоторая последовательность чисел, не превосходящие превосходящих <tex>k</tex>. Возьмём число <tex> j </tex> из второй последовательности, которого нет в первой последовательности. Пусть <tex>F(j) \leqslant k </tex>. Уберём у <tex>j</tex> все подряд идущие единицы в конце двоичной записи, столько же цифр уберём в конце числа <tex>k</tex>. Обозначим их как <tex>j_{0}</tex> и <tex>k_{0}</tex>. Чтобы выполнялось условие <tex>F(j) \leqslant k </tex>, должно выполняться неравенство <tex>j_{0} \leqslant k_{0}</tex>. Но если <tex>j_{0} < k_{0}</tex>, то и <tex>j \leqslant k</tex>, что противоречит условию <tex>j > k</tex>. Значит, <tex>j_{0} = k_{0}</tex>. Но тогда <tex>j</tex> возможно получить по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>, следовательно, <tex>F(j) > k </tex>. Получили противоречие: <tex>j</tex> можно вычислить по формуле, а это значит, что оно содержится в первой последовательности. Таким образом, нужные элементы можно искать по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>.

|style="background-color:#EEE;padding:2px 30px"| <tex>\i_{prev}</tex>

i = nexti | (i+ 1);

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

'''function''' set(i, tx): d = t x - a[i] a[i] = x

Обозначим <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 {{Лемма|statement= sum(i)}</tex> будем действовать следующим образом. Берём <tex> a_i T_i</tex> входит в сумму для , которое является суммой элементов с индексами от <tex> t_k F(i)</tex>, если до <tex> \exists j: k = i </tex>. Теперь к этому значению нужно прибавить <tex>\mid mathrm {sum(F(2^j i) - 1) }</tex>. Аналогично продолжаем складывать, пока не <tex>F(i)</tex> не станет равным <tex>0</tex>. Покажем, что запрос суммы работает за <tex>O(\log{n}}Для доказательства леммы рассмотрим битовую )</tex>. Рассмотрим двоичную запись следующих чисел: числа <tex>i</tex> k - . Функция <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^}{h(k)i} + 1 </tex>. Значит, запрос суммы выполняется за <tex>O(\leqslant i \leqslant k log{n})</tex>.

 Приведем код функции <tex> \mathrm {sum(i) } </tex>:

result = 0;

'''return''' result ==Построение дерева==Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <tex>T_{i}</tex> можно считать быстрее, чем по формуле <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>. Мы можем представить <tex>T_{i}</tex> как сумму нескольких элементов дерева с меньшими индексами и <tex>a_i</tex> (например, <tex>T_{7} = a_{7} + T_{6} + T_{5} + T_{3}</tex>). Рассмотрим, как получается эта сумма. <tex>a_i</tex> элемент не учитывался в предыдущих суммах, поэтому мы его прибавляем к <tex>T_i</tex>. <tex>a_{i-1}</tex> содержится только в <tex>T_{i-1}</tex>, поэтому прибавим <tex>T_{i-1}</tex>. Так как <tex>T_{i-1}</tex> может состоять из нескольких элементов из <tex>A</tex>, то мы пропустим все такие <tex>T_j</tex>, которые содержат элементы из <tex>T_{i-1}</tex>. Мы знаем, что <tex>T_j</tex> содержит <tex>a_j</tex>, поэтому можно пропустить все такие <tex>T_j</tex>, где <tex>j</tex> входит в диапазон от <tex>F(i - 1)</tex> до <tex>i - 2</tex> (индексы элементов <tex>T_{i-1}</tex>). Другими словами, представим каждый элемент массива <tex>T</tex> как столбик (см. картинку). К <tex>a_i</tex> элементу прибавляем <tex>T_{i-1}</tex>. Далее прибавляем такой столбик, верхняя граница которого находится на том же уровне, что нижняя граница предыдущего прибавляемого столбика. Прекращаем складывать, когда нижняя граница нового столбика будет равна <tex>F(i)</tex>.  '''function''' init(i) t[i] = a[i] j = i - 1 '''while''' j >= F(i) t[i] += t[j] j = F(j) - 1 Такое построение будет работать за <tex>O(n \log{n})</tex>.