Á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 Competitive Programming Academy 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy 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 & -iAtualizando 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 & -iConsultando 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 & -iOs 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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
- Árvore de Fenwick para Somas de Prefixos
- Inversões com uma BIT
- Árvore de Segmentos: Construção e Consulta
- Propagação Preguiçosa para Atualizações de Intervalos