Stdlib

This page covers the built-in data structures and their methods. For free functions like sort, gcd, and bsearch, see Builtins.

The compiler only emits the code you actually use. If you call wgraph and only use dijkstra(), the generated C++ will not include bellman-ford, floyd, MST, or any other unused algorithm.

Graph

Constructors:

g = graph(n)
g = graph(n, undirected = true)

Members and methods:

Surface	Purpose
`g.n`	number of nodes
`g.adj`	adjacency lists
`g.add(u, v)`	add an edge
`g.bfs(src)`	breadth-first search
`g.topo()`	topological order
`g.scc()`	strongly connected components
`g.bridges()`	bridge edges
`g.articulation_points()`	articulation points
`g.bipartite()`	bipartite coloring result
`g.bipartite_matching(left_size)`	maximum matching from left partition

g.bfs(src) returns an object with:

Surface	Purpose
`res.dist`	distance array
`res.parent`	parent array
`res.path(dst)`	reconstructed path

g.bipartite_matching(left_size) assumes nodes [0, left_size) are on the left and nodes [left_size, n) are on the right. It returns an object with:

Surface	Purpose
`res.size`	matching cardinality
`res.match_left`	matched right node for each left node, or `-1`
`res.match_right`	matched left node for each right node, or `-1`
`res.pairs()`	matched edge list as `(left, right)` pairs

Weighted graph

Constructors:

wg = wgraph(n)
wg = wgraph(n, undirected = true)

Members and methods:

Surface	Purpose
`wg.n`	number of nodes
`wg.adj`	weighted adjacency lists
`wg.add(u, v, w)`	add a weighted edge
`wg.dijkstra(src)`	Dijkstra result
`wg.zero_one_bfs(src)`	0-1 BFS result
`wg.bellman_ford(src)`	Bellman-Ford result
`wg.floyd()`	all-pairs shortest paths
`wg.mst()`	minimum spanning tree

Result objects:

wg.dijkstra(src) exposes dist, parent, and path(dst)
wg.zero_one_bfs(src) exposes dist, parent, and path(dst)
wg.bellman_ford(src) exposes dist and has_neg_cycle
wg.floyd() exposes dist
wg.mst() exposes cost and edges

Tree

t = tree(n)
t.add(u, v)
t.build(root)

Surface	Purpose
`t.depth`	node depths
`t.parent`	immediate parent
`t.subtree`	subtree sizes
`t.tin`, `t.tout`	Euler-tour entry/exit times
`t.is_ancestor(u, v)`	ancestry test
`t.kth_ancestor(v, k)`	binary-lift jump
`t.lca(u, v)`	lowest common ancestor
`t.dist(u, v)`	tree distance

DSU

d = dsu(n)

Method	Purpose
`d.unite(x, y)`	merge components
`d.find(x)`	root of `x`
`d.same(x, y)`	connectivity test
`d.size(x)`	component size
`d.components()`	number of components

Segment tree

st = segtree(n, op = max)
st = segtree(a, op = sum)

Supported reducers: sum, max, min, gcd, prod

Method	Purpose
`st.build(a)`	build from an array
`st.update(i, val)`	point update
`st.query(l, r)`	range query on `[l, r)`

Lazy segment tree

st = lazy_segtree(n, op = sum)
st = lazy_segtree(a, op = max)

Supported reducers: sum, max, min

This helper is specifically for range-add queries. It does not support arbitrary lazy operations.

Method	Purpose
`st.range_add(l, r, delta)`	add to every value on `[l, r)`
`st.query(l, r)`	range query on `[l, r)`

Fenwick tree

b = bit(n)

Method	Purpose
`b.add(i, val)`	add to one position
`b.sum(l, r)`	sum on `[l, r)`
`b.lower_bound(target)`	first index whose prefix sum reaches `target`
`b.kth(k)`	alias for `lower_bound(k)`

Sparse table

sp = sparse(a, op = min)

Supported reducers: min, max, gcd

Method	Purpose
`sp.query(l, r)`	query on `[l, r)`

Use sparse tables for static arrays only.

Prefix-sum helpers

ps = a.prefix_sum()
ss = a.suffix_sum()
p2d = mat.prefix_sum_2d()
pre = prefix(a, op = sum)
suf = suffix(a, op = gcd)
p2d = prefix_2d(mat, op = sum)
pre = prefix(a, init = 1, reducer = |acc: int, x: int| acc * x)

Surface	Purpose
`ps.query(l, r)`	sum on `[l, r)`
`ss.query(l, r)`	suffix-based query on `[l, r)`
`p2d.query(r1, c1, r2, c2)`	submatrix sum

prefix_sum, suffix_sum, and prefix_sum_2d are fixed sum helpers.

Raw arrays are also available through:

prefix(a, op = ...) and suffix(a, op = ...) with builtin reducers sum, xor, max, min, and gcd
prefix(a, init = ..., reducer = ...) and suffix(a, init = ..., reducer = ...) for custom folds
prefix_2d(mat, op = sum) as the free-function form of the 2D sum helper

Grid

g = grid(mat)
g = grid(mat, dirs = 8)

Surface	Purpose
`g.neighbors(r, c)`	valid neighbors
`g.id(r, c)`	flatten `(r, c)` to one id
`g.cell(id)`	recover `(row, col)` from id
`g.bfs(sr, sc)`	single-source grid BFS returning `dist` matrix
`g.multi_bfs(starts)`	multi-source BFS returning `dist` matrix
`g.components()`	component labeling returning `count` and `comp` matrix

grid_graph(mat) is a separate function that converts a grid to a Graph object for adjacency-based algorithms like BFS or shortest paths on a graph representation. Use grid() when you want grid-native methods, and grid_graph() when you need a Graph.

Rolling hash

h = strhash(s)

Method	Purpose
`h.query(l, r)`	hash of `s[l..r)`
`h.eq(l1, r1, l2, r2)`	substring equality test

Range values

Range literals produce a range object that can also be used directly:

r = [0, n)

Method	Purpose
`r.contains(x)`	membership test
`r.len()`	number of elements

Multiset

s: multiset[int]

Method	Purpose
`s.insert(x)`	add an element
`s.erase_one(x)`	remove one occurrence of `x`
`s.min()`	smallest element
`s.max()`	largest element
`s.count(x)`	number of occurrences of `x`
`s.size()`	total number of elements
`s.empty()`	true if empty

Container methods

These methods are available on most collection types (set, oset, map, omap, stack, queue, deque, pq):

Method	Purpose
`.size()`	number of elements
`.empty()`	true if empty
`.clear()`	remove all elements

Stack, queue, and deque also support:

Method	Available on
`.push(x)`	stack, queue, deque
`.pop()`	stack, queue, deque
`.top()`	stack, pq
`.front()`	queue, deque
`.back()`	deque

Map and set operations:

Method	Available on
`.insert(x)`	set, oset, multiset
`.erase(x)`	set, oset, map, omap
`.find(x)`	set, oset, map, omap
`.count(x)`	set, oset, map, omap, multiset

Ordered set and map also pass through to their C++ lower/upper bound methods via the escape hatch.