Biblioteca

<p align="center"> <picture> <source media="(prefers-color-scheme: dark)" width="200" srcset="docs/logo_white.png"> <source media="(prefers-color-scheme: light)" width="200" srcset="docs/logo_black.png"> <img alt="ufmg" width="200" src="docs/logo_white.png"> </picture> </p> <h1 align="center"> Biblioteca UFMG <br> <a href="https://opensource.org/license/mit" target="_blank" rel="noopener noreferrer nofollow" style="display:inline-block"><img src="https://img.shields.io/badge/License-MIT-yellow.svg" alt="MIT License" style="max-width: 100%;"></a> <a href="https://github.com/brunomaletta/biblioteca/tree/master/Codigo" target="_blank" rel="noopener noreferrer nofollow" style="display:inline-block"><img src="https://img.shields.io/badge/C%2B%2B-17-blue" alt="C++17" style="max-width: 100%;"></a> <a href="https://github.com/brunomaletta/biblioteca/stargazers"><img src="https://img.shields.io/github/stars/brunomaletta/biblioteca?style=social" alt="GitHub stars"></a> </h1> <p align="center"> <a href="https://brunomaletta.github.io/biblioteca/docs/" target="_blank"><img src="https://img.shields.io/badge/🌐_Online_Notebook-Open-2ea44f?style=for-the-badge"></a> <a href="https://github.com/brunomaletta/biblioteca/blob/master/pdf/biblioteca.pdf" target="_blank"><img src="https://img.shields.io/badge/📄_PDF_Notebook-Open-blue?style=for-the-badge"></a> <a href="https://github.com/brunomaletta/biblioteca/blob/master/pdf/theoretical.pdf" target="_blank"><img src="https://img.shields.io/badge/📚_Theoretical_Guide-Open-purple?style=for-the-badge"></a> </p>

Biblioteca de algoritmos, estruturas de dados e primitivas para Maratona de Programação (ICPC) da UFMG.

Códigos em C++, em maior parte implementados pelos alunos da universidade. Mantida desde 2018.

<details> <summary>Hash</summary>

No PDF, a coluna de hash é o hash de cada linha, exceto se a linha contem um caractere }. Nesse caso, o hash da linha é o hash a partir da linha que fecha o último } da linha atual.

Para ver o hash no vim, seleciona as linhas com Shift+v, e aperta Ctrl+h.

</details>

📚 Conteúdo

🧠 Programação Dinâmica

• Divide and Conquer DP
• Longest Common Subsequence - O(n+m) de memória
• Mochila - O(n+cap) de memória
• SOS DP
• Subset Sum

---

🗂️ Estruturas de Dados

• Segment Tree
  • Segtree Padrão (soma)
  • Segtree 2D (iterativa)
  • Segtreap (equivalente a seg 2D esparsa)
  • Segtree Beats
  • Segtree Colorida (lê os comentários pra saber o que faz)
  • Segtree Esparsa - Lazy
  • Segtree Esparsa - O(q) Memória
  • Segtree Iterativa
  • Segtree Iterativa com Lazy Propagation
  • Segtree de PA
  • Segtree Persistente
  • Segtree Persistente com Lazy
• BIT (Fenwick Tree)
• BIT 2D
• BIT com Soma em Range
• BIT-Sort Tree
• Convex Hull Trick
• Convex Hull Trick Dinâmico
• DSU (e variações)
• Li-Chao Tree
• Li-Chao Tree Lazy
• MergeSort Tree
• Minqueue - Deque
• Minqueue - Stack
• Priority Queue DS
• Order Statistic Set (GCC)
• Range Color
• RMQ <O(n), O(1)>
• Slope Trick
• Sparse Table
• Sparse Table Disjunta
• Splaytree
• Splaytree Implicita
• Split-Merge Set
• Split-Merge Set - Lazy
• SQRT Tree
• Treap
• Treap Implícita
• Treap Implícita Persistente
• Wavelet Tree

---

🌳 Grafos

• LCA/HLD
  • LCA <O(n), O(1)>
  • LCA com Binary Lifting
  • LCA com HLD
  • Heavy-Light Decomposition - Aresta
  • Heavy-Light Decomposition - Vértice
  • Heavy-Light Decomposition sem Update
• LCT
  • Link-cut Tree - Aresta
  • Link-cut Tree - Vertice
  • Link-cut Tree Padrão
• AGM Direcionada (arborescência)
• Articulation Points
• Bellman-Ford
• Block-Cut Tree
• Blossom
• Centro/Diâmetro em Árvore
• Centroid (encontra os centroids da árvore)
• Centroid Decomposition
• Centroid Tree
• Dijkstra
• Dinitz
• Dominator Tree
• [Euler Path / Euler Cycle Linear](https://github.com/brunomaletta/Biblioteca/blo