javascript-algorithms
Árvore Fenwick / Árvore Binária Indexada (Fenwick Tree / Binary Indexed Tree)
Uma árvore Fenwick ou árvore binária indexada é um tipo de estrutura de dados que consegue eficiemente atualizar elementos e calcular soma dos prefixos em uma tabela de números.
Quando comparado com um flat array de números, a árvore Fenwick
alcança um balanceamento muito melhor entre duas operações: atualização
(update) do elemento e cálculo da soma do prefíxo. Em uma flar array
de n números, você pode tanto armazenar elementos quando a soma dos
prefixos. Em ambos os casos, computar a soma dos prefixos requer ou
atualizar um array de elementos também requerem um tempo linear, contudo,
a demais operações podem ser realizadas com tempo constante.
A árvore Fenwick permite ambas as operações serem realizadas com tempo
O(log n).
Isto é possível devido a representação dos números como uma árvore, aonde
os valores de cada nó é a soma dos números naquela sub-árvore. A estrutura
de árvore permite operações a serem realizadas consumindo somente acessos
a nós em O(log n).
Implementação de Nós
Árvore Binária Indexada é representada como um array. Em cada nó da Árvore
Binária Indexada armazena a soma de alguns dos elementos de uma array
fornecida. O tamanho da Árvore Binária Indexada é igual a n aonde n é o
tamanho do array de entrada. Na presente implementação nós utilizados o
tamanho n+1 para uma implementação fácil. Todos os índices são baseados em 1.
Na imagem abaixo você pode ver o exemplo animado da criação de uma árvore
binária indexada para o array [1, 2, 3, 4, 5], sendo inseridos um após
o outro.
