Árvore de Segmentos: Construção e Consulta
Calcule mínimo, máximo ou soma de um intervalo em log n.
Árvore de Segmentos: Construção e Consulta é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 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.
Além da árvore de Fenwick
Uma árvore de Fenwick é excelente para somas, mas uma árvore de segmentos lida com mínimo, máximo, mdc e muito mais. Ela é a ferramenta flexível para consultas de intervalos.
Uma árvore sobre intervalos
Cada nó possui um intervalo do vetor. A raiz cobre tudo; os filhos o dividem ao meio até que as folhas contenham elementos individuais.
Armazenamento baseado em vetor
Armazenamos a árvore em um vetor plano de tamanho 2n ou 4n. O nó 1 é a raiz; os filhos do nó i ficam em 2i e 2i+1.
seg = [0] * (2 * n)As folhas contêm os dados
Na forma iterativa, os valores originais ficam na segunda metade do vetor, nos índices n até 2n-1.
for i in range(n):
seg[n + i] = a[i]Construa de baixo para cima
Cada nó interno é a operação combine aplicada aos seus dois filhos. Preencha-os de n-1 até 1, e toda a árvore estará pronta.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]A operação combine
A função combine define a árvore. Use a adição para somas, o mínimo para encontrar mínimos ou o máximo para encontrar máximos. Troque-a para alterar a consulta.
def combine(x, y):
return min(x, y)Atualize um ponto e depois suba
Para alterar um valor, defina a folha e suba até a raiz, recalculando cada pai a partir dos seus dois filhos no caminho.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Consulte um intervalo semiaberto
As consultas de intervalo percorrem as duas extremidades, incorporando os nós de fronteira à resposta. O intervalo é semiaberto, abrangendo de l até, mas não incluindo, r.
O laço de consulta iterativo
Mova l e r em direção um ao outro. Quando um índice for uma fronteira ímpar, incorpore esse nó antes de avançar o ponteiro.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Logarítmica nas duas extremidades
A construção custa O(n), enquanto cada atualização e consulta custa O(log n). Esse equilíbrio é o que torna as árvores de segmentos tão versáteis.
Tenha atenção ao elemento neutro
Comece o resultado com o elemento neutro da operação: 0 para soma, infinito para mínimo e menos infinito para máximo. O início errado produz respostas erradas.
res = float('inf')Verificação rápida
Onde ficam os dados brutos na árvore iterativa?
Recapitulação: intervalos flexíveis
Você construiu uma árvore de segmentos: folhas na segunda metade, pais como operações combine e atualizações e consultas em O(log n) para soma, mínimo ou máximo. 🌳
Perguntas Frequentes
A aula “Árvore de Segmentos: Construção e Consulta” é grátis?
Sim — o texto completo de “Árvore de Segmentos: Construção e Consulta” é 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 Segmentos: Construção e Consulta”?
Calcule mínimo, máximo ou soma de um intervalo 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 3 de 4.
Quanto tempo leva a aula “Árvore de Segmentos: Construção e Consulta”?
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