Дерево Фенвика
Содержание
Дерево Фенвика, также известное как двоичное индексированное дерево (Binary Indexed Tree, BIT).
Терминология:
a - исходный массив
tree - массив дерева, полученный в результате преобразований массива 'a'
i - индекс массива
k - индекс массива
F(i) - еще не определенный индекс, полученный в реузльтате преобразования индекса `i`. F(i) <= i
F(i) - функция, которую создадим позже.
0 1 2 3 4 5 6 7
a[ 5, 7, 9, 3, 8, 2, 4, 6]
Сумма по текущему индексу содержит данные только с предыдущих индексов, не обязательно с нулевого.
В каждой ячейке реузльтируещего массива хранится сумма ячеек отрезка
k.k- не константное число и может меняться.Т.е. в одной ячейке может храниться сумма за предудущий отрезок длинною 2 символа, а в другой ячейке за отрезок длиною 5 символов.
По вертикали — индексы массива a
По горизонтали — индексы массива tree
($T_i$ является суммой элементов массива a, индексы которых заштрихованы), по вертикали — индексы массива a
В данном примере в tree[1] хранится сумма элементов на отрезве a[0:2] . 2 - потому что последний элемент по индексу не включается.
tree[9] = sum(a[8:10])
tree[7] = sum(a[0:8])
На данном этапе получаем структуру дерева вида: tree[i] = sum(a[F(i):i+1]). Примечание: i+1 - чтобы захватить последний элемент по индексу.
Если мы рассчитаем такое F(i) и умеем считать сумму на префиксе, то сможем находить сумму любого подотрезка за O(logn).
Подсчет префиксных сумм:
def prefix_sum(k):
result = 0
i = k
while i >= 0:
result += tree[i]
i = F(i) - 1