Binary Lifting

Videoaulas

Aula 1

• Exponenciação rápida
• Sparse table

Aula 2

• Binary Lifting na árvore
• Euler tour/LCA

Slides

Slides da aula 1

Slides da aula 2

Códigos e Materiais

Material extra

• [CP-algo] Exponenciação rápida
• [CP-algo] Sparse table
• [CP-algo] Binary Lifting - LCA

Exercícios

Parte 1

• Exercícios de fixação
  • [Exponenciação rápida] Fibonacci
  • [Binary Lifting] Lynyrd Skynyrd
  • [Sparse Table] Friends and Subsequences
• Exercícios intermediários
  • [Exponenciação rápida] Magic Gems
  • [Sparse Table] Fountains
• Exercícios difíceis
  • [Exponenciação rápida] Xor-sequences
  • [Sparse Table] CGCDSSQ
  • [Sparse Table] Imbalanced Array

Parte 2

• Exercícios de fixação
  • [Binary Lifting/Árvore] Company Queries I
  • [LCA] Company Queries II
  • [Binary Lifting/Árvore] Fools and Roads
• Exercícios intermediários
  • [Binary Lifting/Árvore] A and B and Lecture Rooms
  • [Binary Lifting/Grafo funcional] Analysis of Pathes in Functional Graph
  • [DFS] Denouncing Mafia (Subregional 2019)
• Exercícios difíceis
  • [Binary Lifting/Árvore] Party Company (Subregional 2020)
  • [Binary Lifting/Árvore] Minimum spanning tree for each edge