Avançado (Nível 3)

Ávores e estruturas de querying

Há vários tipos de problemas que requerem que certos tipos de consultas e modificações sejam feitas a uma estrutura base, uma sequência de inteiros por exemplo. O problema da range minimum query (ou consultas de mínimos de intervalos) aparece frequentemente como subtarefa de vários problemas, nesta secção aprendemos a resolvê-lo e a resolver problemas semelhantes.

• Árvores de Segmentos

Ávores

As árvores são classes de grafos muito interessantes. Além de tema recorrente de vários problemas, são úteis como modelo algorítmico em várias situações. Veremos alguns temas avançados, sobre como efetuar certas procuras e como calcular dinamicamente certos valores.

• Lowest common ancestor
• Decomposição heavy-light

Tópicos de teoria avançada

Há certos temas cujo interesse em concursos é apenas marginal, ou seja, não é mau saber o que tratam, mas não são normalmente abordados. Ainda assim, podem ser úteis mesmo em problemas que não requerem o seu conhecimento para serem resolvidos, através de intuição extra. Reservamos assim este conjunto de artigos para temas teóricos mais avançados que encaixam nesta descrição.

• Otimização convexa