Competitive Programming Library

PDF Version

Algorithms

Contest

• bash config
• debug
• run
• short template
• template
• vim config

Data Structures

• Segment Tree (Dynamic)

  • Range query sum point sum update
  • Range query max point max assign

• Segment Tree Point Update Range Query

  • Query GCD (bottom up)
  • Query sum (bottom up)
  • Query min (bottom up)
  • Query hash (top down)
  • Query max subarray sum (bottom up)

• Segment Tree Range Update Range Query

  • Increment update query min & max (bottom up)
  • Increment update sum query (top down)
  • Arithmetic progression sum update query sum (top down)

• Sqrt Decomposition

  • two sequence queries

• Bitree 2D

• Convex hull trick

• DSU

• Lichao tree dynamic

• Merge sort tree

• Mex with update

• Ordered set (GNU PBDS)

• Prefix sum 2D

• Venice set (complete)

• Venice set

• Wavelet tree

Dynamic Programming

• Binary knapsack
• Edit distance
• Knapsack
• Longest increasing subsequence
• Money sum
• SOS
• Travelling salesman problem

Extras

• int128t stream
• Binary to gray
• Get permutation cycles
• Max & min check
• Mo's algorithm

Geometry

• Check if a point belong to line segment
• Check if point is inside triangle
• Convex hull
• Polygon lattice points
• Segment intersection

Graphs

• Heavy Light Decomposition (Point Update)

  • Maximum number on path

• 2 SAT

• BFS 01

• Bellman Ford (find negative cycle)

• Bellman Ford

• Biconnected components

• Binary lifting

• Bipartite Graph

• Block Cut tree

• D'Esopo Pape

• Dijkstra (K shortest pahts)

• Dijkstra

• Extra edges to make directed graph fully connected

• Find Bridges

• Find articulation points

• Find bridge tree components

• Find bridges (online)

• Find centroid

• Floyd Warshall

• Function graph

• Kruskal

• Lowest common ancestor (binary lifting)

• Lowest common ancestor (sparse table)

• Maximum flow (Dinic)

• Minimum cost flow

• Minimum vertex cover (already divided)

• Prim

• Shortest path with K edges

• Strongly connected components

• Topological sorting (Kahn)

• Topological sorting (Tarjan)

• Tree diameter (DP)

• Tree isomorphism (non rooted)

• Tree isomorphism (rooted)

Math

• Arithmetic progression sum
• Binomial mod
• Binomial
• Chinese remainder theorem
• Derangement
• Euler phi (in range)
• Euler phi
• FFT convolution and exponentiation
• Factorial factorization
• Factorization (Pollard's rho)
• Factorization
• Fast pow
• Find diophantine equation solution
• Find multiplicatinve inverse
• GCD
• Gauss XOR
• Integer partition
• LCM
• Linear recurrence
• List N elements choose K
• List primes (Sieve of Eratosthenes)
• Matrix exponentiation
• NTT convolution and exponentiation (2 mods)
• NTT convolution and exponentiation
• Polyominoes

Primitives

• Bigint
• Integer Mod
• Matrix

Strings

• Count distinct anagrams
• Double hash range query
• Hash range query
• Hash unsigned long long
• K th digit in digit string
• Longest palindrome substring (Manacher)
• Longest palindrome
• Rabin Karp
• Suffix array
• Suffix automaton
• Trie
• Z function

References & Courses

• KACTL ICPC Code Library

• PauloMiranda98's Library

• Thalisson's Library

• IME algoritmos

• UFMG Library

• SSRS lib

• Macacário

• Competitive Programmer's Handbook

• Algorithms for Competitive Programming

• Competitive Programing Book

• UnBalloon

• Neps Academy

• USACO Guide

• TEP