Propagação Preguiçosa para Atualizações de Intervalos
Adie atualizações de intervalos inteiros.
Propagação Preguiçosa para Atualizações de Intervalos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 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.
O problema da atualização de intervalo
E se uma consulta disser para adicionar 5 a cada elemento de l a r? Visitar cada folha custa O(n) por atualização, lento demais para muitas atualizações de intervalo. 😰
A ideia da propagação adiada
A propagação adiada permite que um nó se lembre de uma alteração pendente sem repassá-la imediatamente aos filhos. O trabalho é adiado até que você realmente precise desses filhos.
Um segundo vetor para o trabalho pendente
Junto com a árvore, mantemos um vetor de pendências. A posição correspondente a cada nó armazena uma atualização que se aplica a todo o intervalo dele, mas ainda não foi propagada para baixo.
lazy = [0] * (4 * n)Aplique a um nó inteiro
Quando uma atualização cobre completamente um nó, ajuste o valor armazenado e acumule a alteração nas pendências; depois, pare. Não é necessário descer pela árvore.
seg[node] += (r - l + 1) * val
lazy[node] += valPropague para baixo antes de descer
Antes de visitar os filhos, propague para baixo qualquer valor pendente para ambos. Assim, os filhos permanecem corretos exatamente quando você os consulta.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Três casos por nó
Em cada nó, o intervalo da consulta é disjunto, cobre o nó completamente ou o cobre parcialmente. Ignore, aplique a alteração pendente ou recorra às duas metades, respectivamente.
As atualizações adiadas continuam logarítmicas
Uma atualização de intervalo toca apenas O(log n) nós, porque os nós completamente cobertos param cedo. Esse é todo o benefício de adiar a propagação. ⚡
Consultas também devem ser propagadas para baixo
As consultas de intervalo também devem ser propagadas para baixo antes da recursão, para que leiam os valores atualizados dos filhos. Esquecer isso é o erro clássico da propagação adiada.
Recalcule de baixo para cima após a recursão
Depois de atualizar os filhos, recombine o pai a partir deles. Esse recálculo de baixo para cima mantém cada nó interno consistente com sua subárvore.
seg[node] = seg[2*node] + seg[2*node+1]Atribuição versus adição
A propagação adiada funciona com muitas operações, mas atribuição e adição são combinadas de formas diferentes. Decida como duas atualizações pendentes serão mescladas antes de implementar.
Quando a propagação adiada vale a pena
Use a propagação adiada somente quando realmente precisar de atualizações de intervalo. Para atualizações pontuais, uma árvore de segmentos comum é mais simples e suficiente.
Verificação rápida
O que deve acontecer antes de recursar nos filhos de um nó?
Recapitulação: atualizações adiadas
Você aprendeu a propagação adiada: armazenar alterações pendentes, propagar para baixo antes de descer, recalcular de baixo para cima depois e obter atualizações de intervalo em O(log n). 🎉
Perguntas Frequentes
A aula “Propagação Preguiçosa para Atualizações de Intervalos” é grátis?
Sim — o texto completo de “Propagação Preguiçosa para Atualizações de Intervalos” é 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 “Propagação Preguiçosa para Atualizações de Intervalos”?
Adie atualizações de intervalos inteiros. 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 4 de 4.
Quanto tempo leva a aula “Propagação Preguiçosa para Atualizações de Intervalos”?
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
- Á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