Principais conceitos abordados na aula
- Somas acumuladas:
- Conheço o conceito de somas acumuladas ("prefix sums")
- Conheço o princípio da inclusão-exclusão e como extender somas acumulas para mais que uma dimensão
- Fenwick Trees (Binary Indexed Trees, a.k.a. BITs):
- Conheço o conceito de uma BIT, a maneira como os nós guardam somas acumuladas e a sua (simples) implementação
- Sei como responder a vários tipos de queries relacionadas com somas, como por exemplo:
- single updates, range queries [rangea(a,b) usando bit(b)-bit(a-1)]
- range updates, single queries [update(a,b,v) usando update(a,v) e update(b+1,-v)]
- range update, range querie [usando duas BITs]
- Compreendo como adaptar para mais dimensões, e em particular para o caso de 2D (uma BIT de BITs)
- Maximum Subarray Problem:
- Conheço o problema de determinar a subsequência contígua de maior soma
- Conheço o algoritmo de Kadane para resolver o problema em tempo linear
Material de Estudo
Principais referências
- Somas acumuladas
- BITs
- Algoritmo de Kadane
[em construção - vou acrescentar aqui mais ligações]
Problemas de Iniciação/Reforço
Pedro Ribeiro - DCC/FCUP |
Último update:
