Skip to content

Files

Segment-Tree-Persisente

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Jun 5, 2024
Sep 11, 2024

Uma Seg Tree Esparsa, só que com persistência, ou seja, pode voltar para qualquer estado anterior da árvore, antes de qualquer modificação.

Os métodos query e update agora recebem um parâmetro a mais, que é a root (versão da árvore) que se deja modificar. Todos os métodos continuam O ( log n ) .

O vetor roots guarda na posição i a root da árvore após o i-ésimo update.

Dica: No construtor da Seg Tree, fazer t.reserve(MAX); Lc.reserve(MAX); Rc.reserve(MAX); roots.reserve(Q); pode ajudar bastante no runtime, pois aloca espaço para os vetores e evita muitas realocações durante a execução. Nesse caso, MAX é geralmente O ( Q log L ) , onde Q é o número de queries e L é o tamanho do intervalo.