AC(AtCoder) Library Document

Library map

Nim-ACL provides AtCoder Library-compatible APIs together with additional competitive-programming algorithms, data structures, and Japanese/English documentation.

Start with the standard APIs

Purpose	Documentation	Main APIs
Range products	Segment Tree	`SegTree`, `prod`, `set`
Lazy propagation	Lazy Segment Tree	`LazySegTree`, `apply`, `prod`
Prefix sums	Fenwick Tree	`FenwickTree`, `add`, `sum`
Convolution	Convolution	`convolution`
Maximum flow	Max Flow	`MFGraph`, `flow`
Minimum-cost flow	Min-Cost Flow	`MCFGraph`, `flow`, `slope`
Disjoint sets	DSU	`DSU`, `merge`, `leader`
Strongly connected components	SCC	`SCCGraph`, `scc`
Strings	String Algorithms	suffix array, LCP, Z algorithm
Modular arithmetic	ModInt	static and dynamic modint

Recently added or substantially improved

Area	API	Purpose
Multidimensional search	KD-tree	nearest neighbor and half-open orthogonal ranges
Computational geometry	Minkowski Sum	Minkowski sum of arbitrary point-set hulls
Set power series	Set Power Series Exp / Log	exponential and logarithm
Flow	Minimum-Cost B-Flow	lower/upper bounds, supplies, demands, and costs
Persistent structures	Persistent Segment Tree	versioned updates and range products
Sequence structures	Implicit Treap	split/merge and sequence operations
Trie	Binary Trie	XOR minimum/maximum and multiset operations
FPS	Formal Power Series facade	a unified entry point for FPS APIs

Additional libraries by category

Category	Documentation
DP optimization	Monotone Minima · Divide and Conquer Optimization · SMAWK
Mathematics and polynomials	Berlekamp–Massey · Polynomial Interpolation · Subset Convolution · FPS
Data structures	Persistent Segment Tree · Implicit Treap · KD-tree · Binary Trie
Graphs	Bipartite Edge Coloring · Minimum-Cost B-Flow
Computational geometry	Minkowski Sum

Guides

Documentation structure

Additional-library pages generally follow this order: general form, parameters and types, preconditions, return values and side effects, example, related APIs, and complexity and implementation.

Guides

How to Install

There is atcoder folder in the ac-library folder, after extracting the zip file.
With g++, you can compile by g++ main.cpp -std=c++14 -I . with putting atcoder folder on the same place as main.cpp.
You should compile with -std=c++14 or -std=c++17.
See Appendix for further details.

Note

The behavior is undefined if the input does not match the constraints.
For simplicity, we abbreviate the types as follows.
unsigned int → uint
long long → ll
unsigned long long → ull
$0^0=1$.
Multiple edges and self-loops are allowed unless specified.

List

#include <atcoder/all> : include everything

Data Structures

Math

Graphs

Appendix

Appendix / FAQ

Test

You can test this Library here.

License

The header files in atcoder folder are licensed under a CC0 license. See atcoder/LICENSE for further details.

Extra / Math

FPS facade import atcoder/extra/math/fps
import atcoder/extra/graph/boruvka

extra/dp

extra/math

extra/geometry

extra/structure

extra/graph

extra/string

extra/algorithm

Japanese API facades (experimental)

Canonical Nim-ACL implementations can also be reached through Japanese import paths and API names.

Japanese API facade index

Tree algorithms

Auxiliary Tree (Virtual Tree)

DP optimization

Curated graph facade

Description	Documentation	Import
Curated graph representation, shortest-path, connectivity, spanning-tree, functional-graph and offline-connectivity modules. Existing direct imports remain supported.	Graph facade	`import atcoder/extra/graph/graph`