146
правок
Изменения
Нет описания правки
|statement=
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>.
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) \leq leqslant k \leq leqslant i</tex> .
|proof=
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) \leq leqslant k \leq leqslant i</tex>.
}}
|statement= <tex> a_i </tex> входит в сумму для <tex> t_k </tex>, если <tex> \exists j: k = i \mid (2^j - 1) </tex>.
}}
Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k)} + 1 \leq leqslant i \leq leqslant k </tex>
{| style="background-color:#CCC;margin:0.5px"
* [http://en.wikipedia.org/wiki/ Wikipedia — Fenwick_tree Fenwick tree]
* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево Фенвика]]
