Principais conceitos abordados na aula
- Range Maximum Query (RMQ):
- Sei o que é problema RMQ e o que pede
- Conheço variantes, como pedir o mínimo ou a soma (RSQ)
- Decomposição em raiz quadrada (sqrt decomposition):
- Sei o que significa decompor um array de tamanho n em "partes" (buckets de tamanho sqrt(n)
- Sei como responder a uma query de RMQ usando sqrt decomposition
- Sei como fazer um single update de RMQ usando sqrt decomposition
- Compreendo como adaptar para variações como por exemplo RSQ.
- Árvores de Segmentos (segments trees):
- Percebo o conceito de segment trees
- Sei como implementar segment trees usando arrays simples
- Sei como responder a uma query de RMQ usando sqrt decomposition
- Sei como fazer um single update de RMQ usando sqrt decomposition
- Compreendo como adaptar a função de merge da segment tree para exemplos mais complicados que RMQ (incluindo guardar vários valores num nó, como por exemplo um vector numa merge sort tree)
- Conheço e percebo o conceito de lazy propagation para fazer um range update
- Conheço e percebo o conceito de offline processing e como posso reordenar queries para fazer um bom uso de segment trees.
- Conheço e percebo o conceito de 2D Segment Trees e como usar "árvores de árvores de segmentos"
Material de Estudo
Principais referências
[em construção - vou acrescentar aqui mais ligações]
Pedro Ribeiro - DCC/FCUP |
Último update:
