0Pricing
Coding Interview Prep · Aula

Árvore de Fenwick para Somas de Prefixos

Atualize um ponto e consulte um prefixo em log n.

Árvore de Fenwick para Somas de Prefixos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

Por que os vetores de prefixos falham

Um vetor simples de somas de prefixos responde a intervalos instantaneamente, mas uma única atualização obriga você a reconstruí-lo. Com muitas atualizações, isso fica lento. ⏱️

Conheça a árvore de Fenwick

A árvore de Fenwick, ou BIT, oferece atualizações pontuais e consultas de prefixo em O(log n). Ela é sua melhor opção para totais acumulados dinâmicos.

Indexada a partir de um

Uma árvore de Fenwick vive em um vetor indexado a partir de 1. Usamos o índice 0 como uma sentinela silenciosa, portanto todos os dados reais começam na posição 1.

tree = [0] * (n + 1)

A magia do bit menos significativo definido

Cada índice representa um bloco de valores. O tamanho do bloco é igual a i & -i, o bit menos significativo definido de i. Esse único truque sustenta toda a árvore.

lowbit = i & -i

Atualizando um único ponto

Para adicionar um valor na posição i, avance pelo bit menos significativo a cada etapa, visitando todos os blocos que contêm i.

while i <= n:
    tree[i] += delta
    i += i & -i

Consultando uma soma de prefixo

Para somar os primeiros i valores, caminhe para trás, subtraindo o bit menos significativo a cada etapa até chegar a zero.

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

Os dois laços são logarítmicos

Cada laço desativa um bit a cada iteração, portanto é executado no máximo log n vezes. É por isso que tanto a atualização quanto a consulta continuam rápidas.

Soma de intervalo a partir de dois prefixos

Quer a soma de l a r? Calcule prefixo(r) menos prefixo(l-1), assim como em um vetor estático de prefixos, mas agora as atualizações também são baratas.

range_sum = query(r) - query(l - 1)

Construindo a árvore

A construção mais simples apenas chama a atualização para cada valor inicial. Isso custa O(n log n) e é bastante rápido para a maioria das competições.

for i, v in enumerate(a, 1):
    update(i, v)

Um uso mínimo de memória

Uma árvore de Fenwick precisa de apenas um vetor de tamanho n+1. Esse uso compacto de memória é parte do motivo pelo qual ela é tão apreciada em competições. 💾

Quando escolher uma BIT

Escolha uma árvore de Fenwick quando você alternar atualizações pontuais com consultas de prefixo ou de soma de intervalos. Ela é curta de programar e difícil de superar.

Verificação rápida

Vamos fixar como os laços se movem.

Recapitulação: fundamentos de BIT

Você conheceu a árvore de Fenwick: indexada a partir de 1, baseada em i & -i, com atualização pontual e consulta de prefixo, ambas em O(log n). Em seguida, vamos usá-la para contar inversões. 🎯

Perguntas Frequentes

A aula “Árvore de Fenwick para Somas de Prefixos” é grátis?

Sim — o texto completo de “Árvore de Fenwick para Somas de Prefixos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Árvore de Fenwick para Somas de Prefixos”?

Atualize um ponto e consulte um prefixo em log n. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Árvore de Fenwick para Somas de Prefixos”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Árvore de Fenwick para Somas de Prefixos
  2. Inversões com uma BIT
  3. Árvore de Segmentos: Construção e Consulta
  4. Propagação Preguiçosa para Atualizações de Intervalos
← Voltar para Coding Interview Prep