Library

define の競プロライブラリです。

C++17想定なので、C++14だとコンパイル通らないかもしれません。とは言ってもC++14でエラーが出るのはstd::gcdくらいなので大して問題はないかな...

全て0-indexedです。

Data Structure

• Union Find
• Binary Indexed Tree
• Lazy Segment Tree
• Segment Tree Beats
• Bit Vector
• Wavelet Matrix
• Heavy Light Decomposition
• Sparse Table
• Splay Tree
• Li Chao Tree
• Persistent Array
• Persistent Union Find
• Partial Persistent UnionFind
• Mo's Algorithm

Graph

• Tree
• Min Cost Flow (Primal Dual)
• Max Flow (Dinic)
• SCC

Math

• modint
• nCk ( $n \leq 10^7$ 程度)
• nCk ( $k$ が小さい時)
• Prime Factor (rho + miller rabin)
• Fast Fourier Transform
• extended Euclid
• CRT

String

• Z Algorithm
• Rolling Hash (mod 2^61-1)
• Suffix Array (SA-IS)
• BWT
• FM-index