Material para Estudo - Semana 03

Olá pessoal,

Durante essa semana foram estudadas estruturas de dados mais complexas que as anteriores, possibilitando todos a resolverem problemas mais complexos. Destacamos a importância de cada equipe ter as estruturas implementadas e bem testadas para levar no dia de qualquer prova!

Assunto: Estruturas de Dados - Parte 2

Bibliografia principal:

• Competitive Programming, capítulo 2 (2.3.2, 2.3.3 e 2.3.4) - Union-Find, Segment Tree e Fenwick Tree
• Top Coder - Disjoint Set Data Structures
• PEGWiki - Segment Tree
• SPOJ - Lazy Propagation
• Top Coder - Range Minimum Query and Lower Common Ancestor
• Top Coder - Binary Indexed Trees

Bibliografia complementar:

• Introduction to Algorithms, capítulo 17 - Amortized Analysis
• Introduction to Algorithms, capítulo 21 - Data Structures for Disjoint Sets
• Introduction to Algorithms, capítulo 12 - Binary Search Trees
• Introduction to Algorithms, capítulo 13 - Red-Black Trees
• Introduction to Algorithms, capítulo 14 - Augmenting Data Structures
• Top Coder - An Introduction to Binary Search and Red-Black Trees

Problemas sugeridos:

• UVa 793 (Network Connections): boa prática de union-find.
• SPOJ BR 8382 (Banco do Faraó): Segment Tree sem Lazy Propagation; é o exemplo do PEGWiki de maximum/minimum subvector sum.
• UVa 11402 (Ahoy, Pirates!): Segment Tree com Lazy Propagation
• UVa 12086 (Potentiometers): exemplo básico de Fenwick Tree.