Algoritmo
Uma árvore de segmentos responde consultas de soma ou mínimo em intervalos e atualiza valores em O(log n); a árvore de Fenwick é a alternativa leve para somas.
Uma árvore de segmentos é uma árvore binária que guarda um resumo, como soma, mínimo ou máximo, de cada intervalo obtido ao dividir um vetor ao meio repetidamente. A raiz cobre o vetor inteiro, cada folha cobre um único elemento e cada nó interno combina seus dois filhos. Assim, qualquer pergunta sobre um intervalo contíguo é respondida combinando poucos nós.
Somas de prefixo respondem somas de intervalo em O(1), mas precisam de O(n) para absorver uma única alteração; um vetor simples é atualizado na hora, mas cada consulta custa O(n). Uma árvore de segmentos faz tanto atualizações pontuais quanto consultas de intervalo em O(log n), por isso é a ferramenta certa quando os valores mudam o tempo todo e as consultas não param de chegar. Com propagação preguiçosa, ela também aceita atualizações de intervalo, como somar um valor a um trecho inteiro, em O(log n).
Comece entendendo onde as somas de prefixo deixam a desejar, desenhe à mão uma árvore pequena e acompanhe quais nós uma consulta e uma atualização percorrem. Depois, escreva você mesmo a implementação iterativa curta e uma árvore de Fenwick, e pratique com problemas clássicos como mínimo em intervalo, contagem de inversões e soma em intervalo com atualizações de intervalo.
Cada nó cuida de um intervalo do vetor e guarda sua soma ou seu mínimo; qualquer operação associativa com elemento neutro cabe na mesma estrutura.
Alterar um elemento recalcula apenas um caminho da folha até a raiz, e uma consulta de intervalo combina no máximo dois nós por nível.
Uma atualização de intervalo deixa uma anotação nos nós que a cobrem e só a repassa aos filhos quando uma operação precisa descer.
Para operações inversíveis como a soma, uma árvore de Fenwick (BIT) alcança a mesma complexidade com um vetor de n + 1 posições e poucos laços curtos.
Uma árvore de segmentos iterativa: os elementos ficam na segunda metade de um vetor de tamanho 2n e cada posição anterior guarda a soma de seus dois filhos. update sobe da folha até a raiz recalculando as somas, e query sobe a partir das duas pontas do intervalo semiaberto [left, right), somando apenas os nós da borda. Ao executar, o programa imprime 26, 17 e 28.
segment_tree.py
class SegmentTree:
"""Iterative segment tree: point update and range sum in O(log n)."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
"""Sum of values[left:right] (half-open range)."""
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
if __name__ == "__main__":
tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(tree.query(2, 6)) # 7 + 9 + 6 + 4 = 26
tree.update(3, 0)
print(tree.query(2, 6)) # 7 + 0 + 6 + 4 = 17
print(tree.query(0, 8)) # 28
python segment_tree.pySeis capítulos que levam você da instalação aos conceitos essenciais de Árvores de segmentos.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Árvores de segmentos.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.