Изменения

Дерево Фенвика

35 байт добавлено, 20:10, 3 мая 2011

Нет описания правки

{{Утверждение

|statement='''Лемма.''' <tex> a_i </tex> входит в сумму для <tex> t_k </tex>, если <tex> \exists j: k = i | \cdots(1 \cdots 1) j </tex> раз.

~~|proof=Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k) + 1} \leq i \leq k </tex>~~

* <tex> k - 2^{h(k) + 1} \rightarrow \cdots (0 \cdots 0) </tex> <br/>

* <tex> i \rightarrow \cdots (\cdots) </tex> <br/>

* <tex> k \rightarrow \cdots (1 \cdots 1)</tex>

}}

Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k) + 1} \leq i \leq k </tex>

{| border="1"

|<tex>k - 2^{h(k) + 1}</tex>

|<tex>\cdots (0 \cdots 0)</tex>

|-

|<tex>i</tex>

|<tex>\cdots (\cdots \cdots)</tex>

|-

|<tex>k</tex>

|<tex>\cdots (1 \cdots 1)</tex>

|}

=== Реализация ===

Приведем код функции <tex> sum(i) </tex> на C++:

<code>

272

правки