61
правка
Изменения
Нет описания правки
'''int32''' greatestBit(x: '''int32'''):
power = 1
'''for''' i = 1..<tex>\ldots\log_2{32}</tex>:
x |= x >> power
power <<= 1
Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.
Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</tex>. Деревом Фенвика называется массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0 .. \ldots n - 1 </tex> и <tex> F(i) </tex> — функция, которую мы определили ранее.
==См. также==
