Arrays de Diferenças para Atualizações de Intervalos
Aplique rapidamente muitas operações de adição em intervalos.
Arrays de Diferenças 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.
Inverta o problema
As somas de prefixos respondem rapidamente a consultas de intervalos. Um array de diferenças inverte essa ideia para aplicar rapidamente muitas atualizações de intervalos. 🔁
A maneira lenta
Adicionar um valor a cada elemento de um intervalo, repetidamente, custa O(n) por atualização. Com q atualizações, esse custo explode.
Armazene as alterações
Em vez de alterar cada célula, registre apenas onde uma alteração começa e onde termina. Marque as extremidades, não o meio.
O que um array de diferenças armazena
Um array de diferenças armazena a diferença entre cada elemento e o anterior. Alterar uma única diferença desloca todo o trecho seguinte.
O truque das duas marcações
Para adicionar v de l a r, adicione v no índice l e subtraia v no índice r + 1. Apenas duas alterações cobrem o intervalo inteiro.
diff[l] += v
diff[r + 1] -= vPor que a subtração
O sinal de mais em l ativa a alteração; o sinal de menos em r + 1 a desativa. Juntos, eles limitam a atualização a um único intervalo.
Aplique todas as atualizações com baixo custo
Cada atualização consiste apenas em duas escritas no vetor, então q atualizações levam O(q) no total. O trabalho pesado fica para o final.
Reconstrua o vetor final
Depois de colocar todas as marcações, faça uma soma de prefixos do array de diferenças. Essa única passagem reconstrói cada valor final.
for i in range(1, n):
diff[i] += diff[i - 1]Dimensione com uma posição de proteção
Faça o vetor ter uma célula a mais para que r + 1 nunca ultrapasse o fim. Essa posição extra de proteção evita erros de índice.
O custo total
Você gasta O(q) marcando as atualizações e faz uma passagem O(n) para reconstruir o vetor. O custo combinado é muito menor que o O(n vezes q) ingênuo.
Onde ele se destaca
Arrays de diferenças são excelentes para contagens de reservas, pedágios rodoviários e qualquer problema com muitas operações de adição em intervalos e uma única leitura final.
Verificação rápida
Você adiciona v a cada elemento do índice l ao r.
Recapitulação
Você pode agrupar atualizações de intervalos com um array de diferenças: marque l e r + 1 e depois faça uma soma de prefixos para reconstruir o vetor. Atualizações rápidas, uma única leitura. ✅
Perguntas Frequentes
A aula “Arrays de Diferenças para Atualizações de Intervalos” é grátis?
Sim — o texto completo de “Arrays de Diferenças 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 “Arrays de Diferenças para Atualizações de Intervalos”?
Aplique rapidamente muitas operações de adição em intervalos. 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 “Arrays de Diferenças 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
- Crie um Array de Somas de Prefixos
- Some Qualquer Intervalo com Subtração
- Conte Subarrays com uma Soma-Alvo
- Arrays de Diferenças para Atualizações de Intervalos