ReferenceLibrary
Library
Every public item in the 36 modules of the 0.3 standard library.
Generated from spec/std by cpl doc --format json. Costs and traps follow the doc standard.
Modules
- algebra (46 items)
- bag (15 items)
- beats (3 items)
- bitset (18 items)
- deque (6 items)
- dp (28 items)
- dsu (17 items)
- fenwick (11 items)
- flow (50 items)
- geometry (175 items)
- graph (102 items)
- grid (9 items)
- hashmap (6 items)
- heap (15 items)
- interval (7 items)
- io (4 items)
- lazy (22 items)
- marks (13 items)
- math (97 items)
- matrix (23 items)
- mod (21 items)
- ntt (28 items)
- pair (2 items)
- persistent (7 items)
- poly (49 items)
- prefix (18 items)
- rand (1 items)
- segtree (17 items)
- seq (199 items)
- slope (6 items)
- sparse (9 items)
- strings (100 items)
- subset (5 items)
- timetree (6 items)
- tree (54 items)
- window (14 items)
A to Z
| Item | Module | Cost |
|---|---|---|
Action | algebra | |
Action.new | algebra | O(1) |
Action.of | algebra | O(1) |
AddAction | algebra | |
Affine | algebra | |
Affine.eval | algebra | O(1) |
Affine.id | algebra | O(1) |
Affine.monoid | algebra | O(1) |
Affine.then | algebra | O(1) |
AffineAction | algebra | |
AhoCorasick | strings | |
AhoCorasick.counts | strings | |
AhoCorasick.exit_link | strings | O(1) |
AhoCorasick.fail_order | strings | O(states) |
AhoCorasick.find_all | strings | |
AhoCorasick.hit | strings | |
AhoCorasick.len | strings | O(1) |
AhoCorasick.link | strings | |
AhoCorasick.new | strings | |
AhoCorasick.pattern_state | strings | O(1) |
AhoCorasick.root | strings | O(1) |
AhoCorasick.step | strings | |
AhoCorasick.words_at | strings | |
Anchor | seq | |
Arc | flow | |
Arc.rev | flow | O(1) |
Arena | marks | |
Arena.alloc | marks | O(1) amortized |
Arena.clear | marks | O(1) |
Arena.get | marks | O(1) |
Arena.is_empty | marks | O(1) |
Arena.len | marks | O(1) |
Arena.new | marks | O(cap) |
Arena.reserve | marks | O(cap) |
Arena.set | marks | O(1) |
ArithDiff | prefix | |
ArithDiff.add | prefix | O(1) |
ArithDiff.add_arith | prefix | O(1) |
ArithDiff.finish | prefix | O(|D|) time and space |
ArithDiff.new | prefix | O(|D|) time and space |
AssignAction | algebra | |
AugSortedBag | bag | |
AugSortedBag.add | bag | O(log n) expected |
AugSortedBag.all | bag | O(1) |
AugSortedBag.count | bag | O(log n) expected |
AugSortedBag.drop_min | bag | |
AugSortedBag.each | bag | O(1) amortized per step |
AugSortedBag.extreme | bag | |
AugSortedBag.first | bag | O(1) |
AugSortedBag.fold_between | bag | O(log n) expected |
AugSortedBag.fold_from | bag | |
AugSortedBag.fold_ge | bag | O(log n) expected |
AugSortedBag.fold_gt | bag | O(log n) expected |
AugSortedBag.fold_le | bag | O(log n) expected |
AugSortedBag.fold_lt | bag | O(log n) expected |
AugSortedBag.fold_upto | bag | |
AugSortedBag.is_empty | bag | O(1) |
AugSortedBag.last | bag | O(1) |
AugSortedBag.len | bag | O(1) |
AugSortedBag.merge | bag | |
AugSortedBag.new | bag | O(1) |
AugSortedBag.nth | bag | O(log n) expected |
AugSortedBag.pull | bag | |
AugSortedBag.rank | bag | O(log n) expected |
AugSortedBag.rank_le | bag | |
AugSortedBag.remove | bag | O(log n) expected |
AugSortedBag.reserve | bag | O(cap) when the pool grows, O(1) otherwise |
AugSortedBag.size | bag | |
AugSortedBag.split | bag | |
AugSortedBag.sub | bag | |
AugSortedSet | bag | |
AugSortedSet.add | bag | O(log n) expected |
AugSortedSet.all | bag | O(1) |
AugSortedSet.contains | bag | O(log n) expected |
AugSortedSet.each | bag | O(1) amortized per step |
AugSortedSet.first | bag | O(1) |
AugSortedSet.fold_between | bag | O(log n) expected |
AugSortedSet.fold_ge | bag | O(log n) expected |
AugSortedSet.fold_gt | bag | O(log n) expected |
AugSortedSet.fold_le | bag | O(log n) expected |
AugSortedSet.fold_lt | bag | O(log n) expected |
AugSortedSet.is_empty | bag | O(1) |
AugSortedSet.last | bag | O(1) |
AugSortedSet.len | bag | O(1) |
AugSortedSet.new | bag | O(1) |
AugSortedSet.nth | bag | O(log n) expected |
AugSortedSet.rank | bag | O(log n) expected |
AugSortedSet.remove | bag | O(log n) expected |
AugSortedSet.reserve | bag | O(cap) when the pool grows, O(1) otherwise |
BagCursor | bag | |
Barrett | mod | |
Barrett.mul | mod | O(1) |
Barrett.new | mod | O(1) |
Barrett.reduce | mod | O(1) |
BeatsSegTree | beats | |
BeatsSegTree.add | beats | O(log |D|) |
BeatsSegTree.add_rec | beats | |
BeatsSegTree.all_max | beats | O(1) |
BeatsSegTree.all_min | beats | O(1) |
BeatsSegTree.all_sum | beats | O(1) |
BeatsSegTree.apply_add | beats | |
BeatsSegTree.apply_chmax | beats | |
BeatsSegTree.apply_chmin | beats | |
BeatsSegTree.assign | beats | O(log |D|) amortized |
BeatsSegTree.build | beats | |
BeatsSegTree.chdiv | beats | O(log |D| log V) amortized |
BeatsSegTree.chmax | beats | O(log |D|) amortized; O(log^2 |D|) amortized when mixed with add |
BeatsSegTree.chmax_rec | beats | |
BeatsSegTree.chmin | beats | O(log |D|) amortized; O(log^2 |D|) amortized when mixed with add |
BeatsSegTree.chmin_rec | beats | |
BeatsSegTree.chmod | beats | O(log |D| log V) amortized |
BeatsSegTree.div_rec | beats | |
BeatsSegTree.get | beats | O(log |D|) |
BeatsSegTree.max_rec | beats | |
BeatsSegTree.max_val | beats | O(log |D|) |
BeatsSegTree.min_rec | beats | |
BeatsSegTree.min_val | beats | O(log |D|) |
BeatsSegTree.new | beats | O(|D|) |
BeatsSegTree.pull | beats | |
BeatsSegTree.push | beats | |
BeatsSegTree.set | beats | O(log |D|) |
BeatsSegTree.sum | beats | O(log |D|) |
BeatsSegTree.sum_rec | beats | |
BigInt | math | |
BigInt.abs | math | O(n) |
BigInt.add | math | |
BigInt.div | math | |
BigInt.divmod | math | O(n * m) |
BigInt.from_int | math | O(1) |
BigInt.from_str | math | O(s.len) |
BigInt.gcd | math | O(n^2) |
BigInt.lt | math | |
BigInt.mul | math | |
BigInt.neg | math | |
BigInt.show | math | |
BigInt.sub | math | |
BigInt.to_str | math | O(n) |
BitMat | matrix | |
BitMat.det | matrix | O(n^3 / 64) |
BitMat.get | matrix | O(1) |
BitMat.identity | matrix | O(n^2 / 64) time and space |
BitMat.inverse | matrix | O(n^3 / 64) |
BitMat.mul | matrix | O(rows * cols * o.cols / 64) |
BitMat.new | matrix | O(rows * cols / 64) time and space |
BitMat.rank | matrix | O(rows * cols * min(rows, cols) / 64) |
BitMat.set | matrix | O(1) |
BitMat.solve | matrix | O(rows * cols * min(rows, cols) / 64) |
BitMat.solve_space | matrix | O(rows * cols * min(rows, cols) / 64) |
Bitset | bitset | |
Bitset.add | bitset | O(1) |
Bitset.any | bitset | O(K / 64 + visited) words scanned and calls of pred |
Bitset.bitand | bitset | O(K / 64) time and space |
Bitset.bitor | bitset | O(K / 64) time and space |
Bitset.bitxor | bitset | O(K / 64) time and space |
Bitset.clear | bitset | O(K / 64) |
Bitset.complement | bitset | O(K / 64) time and space |
Bitset.contains | bitset | O(1) |
Bitset.count | bitset | O(1) |
Bitset.count_below | bitset | O(K / 64) |
Bitset.count_range | bitset | O(r.len / 64 + 1) |
Bitset.each | bitset | O(K / 64 + len) to walk, O(1) per member amortized |
Bitset.each_rev | bitset | O(K / 64 + len) to walk |
Bitset.empty | bitset | O(K / 64) time and space |
Bitset.find | bitset | O(K / 64 + visited) |
Bitset.first | bitset | O(K / 64) |
Bitset.flip_range | bitset | O(r.len / 64 + 1) |
Bitset.from | bitset | O(K) time, O(K / 64) space |
Bitset.full | bitset | O(K / 64) time and space |
Bitset.intersect | bitset | O(K / 64) |
Bitset.is_empty | bitset | O(1) |
Bitset.len | bitset | O(1) |
Bitset.meets | bitset | O(K / 64), less on an early hit |
Bitset.new | bitset | O(K / 64) time and space |
Bitset.next | bitset | O(K / 64) |
Bitset.nth | bitset | O(K / 64) |
Bitset.of | bitset | O(K / 64 + xs.len) time, O(K / 64) space |
Bitset.prev | bitset | O(K / 64) |
Bitset.recount | bitset | |
Bitset.remove | bitset | O(1) |
Bitset.rfind | bitset | O(K / 64 + visited) |
Bitset.set | bitset | O(K / 64) time and space |
Bitset.set_range | bitset | O(r.len / 64 + 1) |
Bitset.shift_down | bitset | O(K / 64) |
Bitset.shift_or | bitset | O(K / 64) |
Bitset.shift_up | bitset | O(K / 64) |
Bitset.shifted | bitset | O(K / 64) time and space, for any k |
Bitset.single | bitset | O(K / 64) time and space |
Bitset.subset_sums | bitset | O(K sqrt(S) / 64) time, where S is the sum of weights; O(K / 64) space |
Bitset.subtract | bitset | O(K / 64) |
Bitset.symmetric | bitset | O(K / 64) |
Bitset.toggle | bitset | O(1) |
Bitset.trim | bitset | |
Bitset.union | bitset | O(K / 64) |
Bitset.with | bitset | O(K / 64) time and space |
Bitset.without | bitset | O(K / 64) time and space |
Bitset<D>.show | bitset | |
Bitset<D>.sub | bitset | |
BucketCount | bag | |
BucketCount.add | bag | O(1) |
BucketCount.clear | bag | O(r.len) |
BucketCount.count | bag | O(1) |
BucketCount.count_lt | bag | O(sqrt(N)) |
BucketCount.is_empty | bag | O(1) |
BucketCount.kth | bag | O(sqrt(N)) |
BucketCount.len | bag | O(1) |
BucketCount.new | bag | O(r.len) |
BucketCount.remove | bag | O(1) |
ByAngle | geometry | |
ByAngle.lt | geometry | |
ByAngleFrom | geometry | |
ByAngleFrom.lt | geometry | |
Centroids | tree | |
Centroids.ancestors | tree | O(1) per entry, O(log n) in all |
Centroids.depth | tree | O(1) |
Centroids.new | tree | O(n log n) time and memory |
Centroids.parent | tree | O(1) |
Centroids.piece | tree | O(size of the piece) |
Circle | geometry | |
Circle.area | geometry | O(1) |
Circle.circumference | geometry | O(1) |
Circle.locate | geometry | O(1) |
Circle.through | geometry | O(1) |
ColorMatroid | flow | |
ColorMatroid.new | flow | O(1); each rebuild is O(E) |
Comb | mod | |
Comb.arrange | mod | O(1) amortized |
Comb.catalan | mod | O(1) amortized |
Comb.choose | mod | O(1) amortized for n < M.MOD; O(log_P n) otherwise |
Comb.choose_lucas | mod | |
Comb.derange | mod | O(1) amortized, O(n) table |
Comb.ensure | mod | |
Comb.fact | mod | O(1) amortized |
Comb.grow | mod | |
Comb.inv | mod | O(1) amortized |
Comb.inv_fact | mod | O(1) amortized |
Comb.multichoose | mod | O(1) amortized |
Comb.multinomial | mod | O(ks.len) amortized |
Comb.new | mod | O(min(limit, P)) |
Commutative | algebra | |
Complement | graph | |
Complement.out | graph | O(|V| + deg u) |
Compressed | seq | |
Compressed.at | seq | O(log n) |
Compressed.contains | seq | O(log n) |
Compressed.first_ge | seq | O(log n) |
Compressed.first_gt | seq | O(log n) |
Compressed.get | seq | O(1) |
Compressed.last_le | seq | O(log n) |
Compressed.last_lt | seq | O(log n) |
Compressed.len | seq | O(1) |
Compressed.slice | seq | O(r.len) |
Compressed.try_at | seq | O(log n) |
Concave | slope | |
Concave.add_abs | slope | O(log n) expected |
Concave.add_const | slope | O(1) |
Concave.add_left | slope | O(log n) expected |
Concave.add_linear | slope | O(1) |
Concave.add_quadratic | slope | O(1) |
Concave.add_right | slope | O(log n) expected |
Concave.argmax | slope | O(log n) expected (O(n) in the current implementation) |
Concave.at | slope | O(log n) expected (O(c - lo + log n) in the current implementation) |
Concave.count_at_least | slope | |
Concave.flat | slope | O(|r| log |r|) expected |
Concave.hi | slope | O(1) |
Concave.lo | slope | O(1) |
Concave.max | slope | O(log n) expected (O(n) in the current implementation) |
Concave.max_convolve | slope | O(|g| log n) expected, for |g| slopes in g |
Concave.point | slope | O(1) |
Concave.prefix_max | slope | O(log n) expected (O(n log n) in the current implementation) |
Concave.reserve | slope | O(n) |
Concave.shift | slope | O(1) |
Concave.slide_max | slope | O(b - a + log n) expected |
Concave.suffix_max | slope | O(log n) expected (O(n log n) in the current implementation) |
Convex | slope | |
Convex.add_abs | slope | O(log n) expected |
Convex.add_const | slope | O(1) |
Convex.add_left | slope | O(log n) expected |
Convex.add_linear | slope | O(1) |
Convex.add_quadratic | slope | O(1) |
Convex.add_right | slope | O(log n) expected |
Convex.argmin | slope | O(log n) expected (O(n) in the current implementation) |
Convex.at | slope | O(log n) expected (O(c - lo + log n) in the current implementation) |
Convex.flat | slope | O(|r| log |r|) expected |
Convex.hi | slope | O(1) |
Convex.lo | slope | O(1) |
Convex.min | slope | O(log n) expected (O(n) in the current implementation) |
Convex.min_convolve | slope | O(|g| log n) expected, for |g| slopes in g |
Convex.point | slope | O(1) |
Convex.prefix_min | slope | O(log n) expected (O(n log n) in the current implementation) |
Convex.shift | slope | O(1) |
Convex.slide_min | slope | O(b - a + log n) expected |
Convex.suffix_min | slope | O(log n) expected (O(n log n) in the current implementation) |
CostFlow | flow | |
CostFlow.add | flow | O(1) amortized; two arcs of memory |
CostFlow.arcs | flow | O(E) for the whole walk |
CostFlow.cancel_cycles | flow | O(V E log V) worst case, by cost scaling |
CostFlow.cap | flow | O(1) |
CostFlow.cost | flow | O(1) |
CostFlow.flow | flow | O(1) |
CostFlow.min_cost_flow | flow | O(F E log V) for F augmenting paths, plus O(V E) once when a residual arc has a negative cost |
CostFlow.new | flow | O(n) for n = V.count |
CostFlow.potentials | flow | |
CostFlow.set_cap | flow | O(1) |
CostFlow.slope | flow | as min_cost_flow |
CostFlow.source | flow | O(1) |
CostFlow.target | flow | O(1) |
Counter | hashmap | |
Counter.absorb | hashmap | O(min(|self|, |other|)) expected |
Counter.add | hashmap | O(1) expected amortized |
Counter.clear | hashmap | O(n) |
Counter.contains | hashmap | O(1) expected |
Counter.get | hashmap | O(1) expected |
Counter.is_empty | hashmap | O(1) |
Counter.items | hashmap | O(1) to make, O(1) per step |
Counter.keys | hashmap | O(1) to make, O(1) per step |
Counter.len | hashmap | O(1) |
Counter.most_common | hashmap | O(n log n) |
Counter.new | hashmap | O(1) |
Counter.of | hashmap | O(n) expected |
Counter.remove | hashmap | O(1) expected |
Counter.reserve | hashmap | O(cap) when the table grows, O(1) otherwise |
Counter.set | hashmap | O(1) expected amortized |
Counter.take | hashmap | O(1) |
Counter.total | hashmap | O(n) |
Counter.values | hashmap | O(1) to make, O(1) per step |
Counter<K, Int>.pop | window | |
Counter<K, Int>.push | window | |
Curved | ntt | |
Deque | deque | |
Deque.clear | deque | O(1) |
Deque.each | deque | O(1) per step |
Deque.each_rev | deque | O(1) per step |
Deque.first | deque | O(1) |
Deque.get | deque | O(1) |
Deque.grow_to | deque | |
Deque.is_empty | deque | O(1) |
Deque.items | deque | O(1) to make, O(1) per step |
Deque.last | deque | O(1) |
Deque.len | deque | O(1) |
Deque.new | deque | O(1); nothing is allocated until the first push |
Deque.of | deque | O(n) |
Deque.pop | deque | O(1) |
Deque.pop_front | deque | O(1) |
Deque.pop_front_while | deque | O(k) for k removed |
Deque.pop_while | deque | O(k) for k removed |
Deque.push | deque | O(1) amortized; a full ring doubles |
Deque.push_front | deque | O(1) amortized; a full ring doubles |
Deque.reserve | deque | O(1) when empty, O(cap) otherwise |
Deque.rotate_left | deque | O(min(k, n - k)) after reducing k mod n |
Deque.rotate_right | deque | O(min(k, n - k)) after reducing k mod n |
Deque.set | deque | O(1) |
Deque.take | deque | O(1) |
Deque.to_list | deque | O(n), one new List |
Desc | algebra | |
Desc<T>.lt | algebra | |
Desc<T>.show | algebra | |
Diff | prefix | |
Diff.add | prefix | O(1) |
Diff.finish | prefix | O(|D|) time and space |
Diff.new | prefix | O(|D|) time and space |
Dir4 | grid | |
Dir4.all | grid | O(1) |
Dir4.back | grid | O(1) |
Dir4.ccw | grid | O(1) |
Dir4.cw | grid | O(1) |
Dir4.delta | grid | O(1) |
Dir4.down | grid | O(1) |
Dir4.from | grid | O(1) |
Dir4.left | grid | O(1) |
Dir4.right | grid | O(1) |
Dir4.up | grid | O(1) |
Dir8 | grid | |
Dir8.all | grid | O(1) |
Dir8.back | grid | O(1) |
Dir8.ccw | grid | O(1) |
Dir8.cw | grid | O(1) |
Dir8.delta | grid | O(1) |
Dir8.from | grid | O(1) |
DirichletSum | math | |
DirichletSum.new | math | O(f_small.len) to build; queries as sum |
DirichletSum.sum | math | O(1) cached; O(n^(2/3)) total across all n / i queries |
Disjoint | ntt | |
DisjointSparseTable | sparse | |
DisjointSparseTable.all | sparse | O(1) |
DisjointSparseTable.fold | sparse | O(1), at most one op call |
DisjointSparseTable.get | sparse | O(1) |
DisjointSparseTable.new | sparse | O(|D| log |D|) time and memory, op called O(|D| log |D|) times |
DisjointSparseTable.try_fold | sparse | O(1) |
Dsu | dsu | |
Dsu.components | dsu | O(1) |
Dsu.find | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
Dsu.find_ord | dsu | |
Dsu.groups | dsu | O(n alpha(n)); allocates the lists |
Dsu.mark | dsu | O(1) |
Dsu.merge | dsu | as unite |
Dsu.new | dsu | O(n) for n = V.count; one [V] array |
Dsu.roots | dsu | O(n) for the whole walk, no allocation |
Dsu.same | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
Dsu.size | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
Dsu.undo_to | dsu | O(1) per undone unite |
Dsu.unite | dsu | O(alpha(n)) amortized; O(log n) after the first mark, plus one log entry |
Dsu<V>.mark | window | |
Dsu<V>.undo_to | window | |
DsuOf | dsu | |
DsuOf.components | dsu | O(1) |
DsuOf.find | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
DsuOf.get | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
DsuOf.groups | dsu | O(n alpha(n)); allocates the lists |
DsuOf.mark | dsu | O(1) |
DsuOf.merge | dsu | as unite |
DsuOf.new | dsu | O(n) calls of init; three [V] arrays |
DsuOf.roots | dsu | O(n) for the whole walk, no allocation |
DsuOf.same | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
DsuOf.set | dsu | O(alpha(n)) amortized; O(log n) after the first mark, plus one log entry |
DsuOf.size | dsu | O(alpha(n)) amortized; O(log n) after the first mark |
DsuOf.undo_to | dsu | O(1) per undone change |
DsuOf.unite | dsu | as Dsu.unite, plus one call of join |
DsuOf.values | dsu | O(n) for the whole walk, no allocation |
DsuOf<V, T>.mark | window | |
DsuOf<V, T>.undo_to | window | |
DualFenwick | fenwick | |
DualFenwick.add | fenwick | O(log |D|) |
DualFenwick.add_at | fenwick | |
DualFenwick.clear | fenwick | O(|D|) |
DualFenwick.get | fenwick | O(log |D|) |
DualFenwick.new | fenwick | O(|D|) time; memory |D| + 1 values |
DynamicAhoCorasick | strings | |
DynamicAhoCorasick.add | strings | O(|pattern| * |A| * log n) amortized |
DynamicAhoCorasick.count_matches | strings | O(|text| * log n) |
DynamicAhoCorasick.is_empty | strings | O(1) |
DynamicAhoCorasick.len | strings | O(1) |
DynamicAhoCorasick.new | strings | O(1) |
DynamicAhoCorasick.remove | strings | O(|pattern| * |A| * log n) amortized |
DynamicHash | strings | |
DynamicHash.all | strings | O(1) |
DynamicHash.get | strings | O(log n) |
DynamicHash.is_empty | strings | O(1) |
DynamicHash.is_palindrome | strings | O(log n) |
DynamicHash.len | strings | O(1) |
DynamicHash.new | strings | O(n) |
DynamicHash.rev_get | strings | O(log n) |
DynamicHash.set | strings | O(log n) |
DynamicOrderTree | segtree | |
DynamicOrderTree.below | segtree | |
DynamicOrderTree.bump | segtree | |
DynamicOrderTree.count_in | segtree | O(log^2 |D|) |
DynamicOrderTree.count_lt | segtree | O(log^2 |D|) |
DynamicOrderTree.get | segtree | O(1) |
DynamicOrderTree.kth | segtree | O(log^2 |D|) |
DynamicOrderTree.new | segtree | O(|D| log^2 |D|) time and memory |
DynamicOrderTree.set | segtree | O(log^2 |D|) |
DynamicOrderTree.span_count | segtree | |
DynBitset | bitset | |
DynBitset.add | bitset | O(1) |
DynBitset.cap | bitset | O(1) |
DynBitset.clear | bitset | O(cap / 64) |
DynBitset.contains | bitset | O(1) |
DynBitset.count_below | bitset | O(cap / 64) |
DynBitset.count_range | bitset | O(r.len / 64 + 1) |
DynBitset.each | bitset | O(cap / 64 + len) to walk |
DynBitset.each_rev | bitset | O(cap / 64 + len) to walk |
DynBitset.first | bitset | O(cap / 64) |
DynBitset.full | bitset | O(cap / 64) time and space |
DynBitset.intersect | bitset | O(cap / 64) |
DynBitset.is_empty | bitset | O(1) |
DynBitset.last | bitset | O(cap / 64) |
DynBitset.len | bitset | O(1) |
DynBitset.meets | bitset | O(cap / 64), less on an early hit |
DynBitset.new | bitset | O(cap / 64) time and space |
DynBitset.next | bitset | O(cap / 64) |
DynBitset.nth | bitset | O(cap / 64) |
DynBitset.prev | bitset | O(cap / 64) |
DynBitset.recount | bitset | |
DynBitset.remove | bitset | O(1) |
DynBitset.resize | bitset | O(new_cap / 64) time and space |
DynBitset.set | bitset | O(1) |
DynBitset.shift_down | bitset | O(cap / 64) |
DynBitset.shift_or | bitset | O(cap / 64) |
DynBitset.shift_up | bitset | O(cap / 64) |
DynBitset.subset_sums | bitset | O(cap sqrt(S) / 64) time, where S is the sum of weights; O(cap / 64) space |
DynBitset.subtract | bitset | O(cap / 64) |
DynBitset.symmetric | bitset | O(cap / 64) |
DynBitset.toggle | bitset | O(1) |
DynBitset.trim | bitset | |
DynBitset.union | bitset | O(cap / 64) |
Edge | graph | |
Edged | graph | |
Edged.e | graph | O(1) |
EdgedNext | graph | |
ErasableHeap | heap | |
ErasableHeap.clear | heap | O(1) |
ErasableHeap.is_empty | heap | O(1) |
ErasableHeap.len | heap | O(1) |
ErasableHeap.new | heap | O(1) |
ErasableHeap.peek | heap | O(log n) amortized |
ErasableHeap.pop | heap | O(log n) amortized |
ErasableHeap.prune | heap | |
ErasableHeap.push | heap | O(log n) |
ErasableHeap.remove | heap | O(log n) |
ErasableHeap.take | heap | O(1) |
EulerTourTree | tree | |
EulerTourTree.connected | tree | expected O(log n) |
EulerTourTree.cut | tree | expected O(log n) |
EulerTourTree.fold_sub | tree | expected O(log n) |
EulerTourTree.fold_tree | tree | expected O(log n) |
EulerTourTree.get | tree | O(1) |
EulerTourTree.len | tree | expected O(log n) |
EulerTourTree.link | tree | expected O(log n) |
EulerTourTree.new | tree | O(n) |
EulerTourTree.set | tree | expected O(log n) |
Events | tree | |
Events.enter | tree | O(1) |
Events.exit | tree | O(1) |
Events.path | tree | O(log n) |
Events.sub | tree | O(1) |
Fenwick | fenwick | |
Fenwick.add | fenwick | O(log |D|) |
Fenwick.all | fenwick | O(1) |
Fenwick.clear | fenwick | O(|D|) |
Fenwick.first_ge | fenwick | O(log |D|) |
Fenwick.first_gt | fenwick | O(log |D|) |
Fenwick.fold | fenwick | O(log |D|) |
Fenwick.get | fenwick | O(log |D|) |
Fenwick.kth | fenwick | O(log |D|) |
Fenwick.new | fenwick | O(|D|) time; memory |D| + 1 values |
Fenwick.prefix | fenwick | O(log |D|) |
Fenwick.set | fenwick | O(log |D|) |
Fenwick.suffix | fenwick | O(log |D|) |
Fenwick2D | fenwick | |
Fenwick2D.add | fenwick | O(log |R| log |C|) |
Fenwick2D.clear | fenwick | O(|R| |C|) |
Fenwick2D.corner | fenwick | |
Fenwick2D.fold | fenwick | O(log |R| log |C|) |
Fenwick2D.get | fenwick | O(log |R| log |C|) |
Fenwick2D.new | fenwick | O(|R| |C|) time; memory (|R| + 1)(|C| + 1) values |
Fenwick2D.prefix | fenwick | O(log |R| log |C|) |
FillOrder | prefix | |
FillPrefix | prefix | |
FillPrefix.fold | prefix | O(1) |
FillPrefix.prefix | prefix | O(1) |
FillPrefix.set | prefix | O(1) |
Filtered | seq | |
Filtered.src | seq | O(1) |
FlatMap | hashmap | |
FlatMap.absorb | hashmap | O(min(|self|, |other|)) expected |
FlatMap.clear | hashmap | O(capacity) |
FlatMap.contains | hashmap | O(1) expected |
FlatMap.get | hashmap | O(1) expected |
FlatMap.get_or_insert | hashmap | O(1) expected amortized |
FlatMap.is_empty | hashmap | O(1) |
FlatMap.items | hashmap | O(1) to make, O(capacity) to walk |
FlatMap.keys | hashmap | O(1) to make, O(capacity) to walk |
FlatMap.len | hashmap | O(1) |
FlatMap.new | hashmap | O(cap) |
FlatMap.rehash | hashmap | |
FlatMap.remove | hashmap | O(1) expected |
FlatMap.reserve | hashmap | O(cap) when the table grows, O(1) otherwise |
FlatMap.set | hashmap | O(1) expected amortized |
FlatMap.slot | hashmap | |
FlatMap.take | hashmap | O(1) |
FlatMap.values | hashmap | O(1) to make, O(capacity) to walk |
Flip | lazy | |
Flip.of | lazy | O(1) |
Flip.op | lazy | O(1) |
FlipAction | algebra | |
FlowGraph | flow | |
FlowGraph.add | flow | O(1) amortized; two arcs of memory |
FlowGraph.add_both | flow | O(1) amortized; two arcs of memory |
FlowGraph.arcs | flow | O(E) for the whole walk |
FlowGraph.augment | flow | |
FlowGraph.cap | flow | O(1) |
FlowGraph.close | flow | |
FlowGraph.cut_arcs | flow | O(V + E) |
FlowGraph.flow | flow | O(1) |
FlowGraph.levels | flow | |
FlowGraph.max_flow | flow | O(V² E); O(E sqrt V) when every capacity is 1 |
FlowGraph.min_cut | flow | O(V + E) |
FlowGraph.new | flow | O(n) for n = V.count |
FlowGraph.out | flow | O(deg u) for the whole walk |
FlowGraph.paths | flow | O(P (V + E)) for P paths |
FlowGraph.push | flow | |
FlowGraph.push_relabel | flow | O(V² sqrt E) |
FlowGraph.reset | flow | O(E) |
FlowGraph.residual | flow | O(1) |
FlowGraph.set_cap | flow | O(1) |
FlowGraph.source | flow | O(1) |
FlowGraph.target | flow | O(1) |
Functional | graph | |
Functional<V>.after | graph | O(log k) |
Functional<V>.cycle_len | graph | O(1) |
Functional<V>.cycles | graph | O(n) |
Functional<V>.depth | graph | O(1) |
Functional<V>.dist | graph | O(log n) |
Functional<V>.jump_while | graph | O(log n) |
Functional<V>.lift | graph | |
Functional<V>.new | graph | O(n log n) |
Functional<V>.on_cycle | graph | O(1) |
Functional<V>.root_of | graph | O(1) |
Graph | graph | |
Graph.at | graph | O(1) |
Graph.deg | graph | O(1) |
Graph.dfs_tree | graph | O(n + m) |
Graph.directed | graph | O(n + m) time and memory, plus m calls of keep |
Graph.edges | graph | O(1) to make, O(1) per edge |
Graph.has | graph | O(deg u) |
Graph.hops | graph | O(n (n + m)) time, O(n^2) memory |
Graph.lists | graph | O(n + m) |
Graph.matrix | graph | O(n^2 + m) time, O(n^2) memory |
Graph.next | graph | O(1) per vertex yielded |
Graph.of | graph | O(n + m) |
Graph.only | graph | O(1) to make; keep and from run per arc walked |
Graph.out | graph | O(1) to make, O(1) per arc |
Graph.peel | graph | O(n + m) plus the calls of ready and on_remove |
Graph.spanning_tree | graph | O(n + m) |
Graph.transpose | graph | O(n + m) |
Graph.undirected | graph | O(n + m) time and memory, plus 2m calls of keep |
Graph.weighted | graph | O(1) to make; f runs on every arc read |
GraphicMatroid | flow | |
GraphicMatroid.new | flow | O(1); each rebuild is O(E alpha(V)) |
Group | algebra | |
Group.of | algebra | O(1) |
HalfPlane | geometry | |
HalfPlane.from_line | geometry | O(1) |
HalfPlane.side | geometry | O(1) |
HalfPlane.through | geometry | O(1) |
Hash2D | strings | |
Hash2D.new | strings | |
Hash2D.rect | strings | |
Hash61 | strings | |
Hashable | strings | |
Hashable.hash_token | strings | |
HashVal | strings | |
HashVal.hash_token | strings | O(1) |
HasId | algebra | |
HasId.id | algebra | |
HasInv | algebra | |
HasInv.inv | algebra | |
Heap | heap | |
Heap.clear | heap | O(1) |
Heap.drain | heap | O(log n) per step |
Heap.is_empty | heap | O(1) |
Heap.len | heap | O(1) |
Heap.less | heap | |
Heap.new | heap | O(1) |
Heap.of | heap | O(n) |
Heap.peek | heap | O(1) |
Heap.pop | heap | O(log n) |
Heap.push | heap | O(log n), amortized over list growth |
Heap.push_all | heap | O(k log n) for k items |
Heap.push_pop | heap | O(log n); O(1) when x is returned |
Heap.replace_top | heap | O(log n) |
Heap.reserve | heap | O(cap) when the storage grows, O(1) otherwise |
Heap.sift_down | heap | |
Heap.take | heap | O(1) |
HistoricBeatsSegTree | beats | |
HistoricBeatsSegTree.add | beats | O(log |D|) |
HistoricBeatsSegTree.apply | beats | |
HistoricBeatsSegTree.ask | beats | |
HistoricBeatsSegTree.build | beats | |
HistoricBeatsSegTree.chmax | beats | O(log |D|) amortized; O(log^2 |D|) amortized when mixed with add |
HistoricBeatsSegTree.chmin | beats | O(log |D|) amortized; O(log^2 |D|) amortized when mixed with add |
HistoricBeatsSegTree.compose | beats | |
HistoricBeatsSegTree.give | beats | |
HistoricBeatsSegTree.hist_max | beats | O(log |D|) |
HistoricBeatsSegTree.hist_sum | beats | O(log |D|) |
HistoricBeatsSegTree.max_val | beats | O(log |D|) |
HistoricBeatsSegTree.new | beats | O(|D|) |
HistoricBeatsSegTree.pull | beats | |
HistoricBeatsSegTree.push | beats | |
HistoricBeatsSegTree.query | beats | |
HistoricBeatsSegTree.sum | beats | O(log |D|) |
HistoricBeatsSegTree.upd | beats | |
HistoricBeatsSegTree.update | beats | |
Id | marks | |
Idempotent | algebra | |
IncrementalBridges | graph | |
IncrementalBridges<V>.add | graph | O(log n) amortized |
IncrementalBridges<V>.new | graph | O(n) |
IncrementalBridges<V>.same | graph | O(alpha) |
IncrementalBridges<V>.two_edge_same | graph | O(alpha) |
IndexedHeap | heap | |
IndexedHeap.before | heap | |
IndexedHeap.clear | heap | O(len) |
IndexedHeap.contains | heap | O(1) |
IndexedHeap.decrease | heap | O(log n) |
IndexedHeap.get | heap | O(1) |
IndexedHeap.increase | heap | O(log n) |
IndexedHeap.is_empty | heap | O(1) |
IndexedHeap.len | heap | O(1) |
IndexedHeap.new | heap | O(|D|) |
IndexedHeap.peek | heap | O(1) |
IndexedHeap.pop | heap | O(log n) |
IndexedHeap.remove | heap | O(log n) |
IndexedHeap.set | heap | O(log n) |
IndexedHeap.sift_down | heap | |
IndexedHeap.sift_up | heap | |
IndexedHeap.swap_at | heap | |
Interner | marks | |
Interner.clear | marks | O(1) |
Interner.contains | marks | O(1) expected |
Interner.get | marks | O(1) expected |
Interner.id | marks | O(1) expected |
Interner.is_empty | marks | O(1) |
Interner.key | marks | O(1) |
Interner.len | marks | O(1) |
Interner.new | marks | O(1) |
Interner.reserve | marks | O(cap) |
IntervalMap | interval | |
IntervalMap.assign | interval | O((1 + overwritten) log runs) amortized |
IntervalMap.assign_point | interval | O(log runs) |
IntervalMap.each | interval | O(1) per run |
IntervalMap.each_rev | interval | O(1) per run |
IntervalMap.first_where | interval | O(log runs + skipped) for skipped runs that fail ok |
IntervalMap.from | interval | O(|D|) |
IntervalMap.get | interval | O(log runs) |
IntervalMap.new | interval | O(1) |
IntervalMap.range | interval | O(log runs + k) for k pieces |
IntervalMap.run_at | interval | O(log runs) |
IntervalMap.runs | interval | O(1) |
IntervalMap.set | interval | O(log runs) |
IntervalSet | interval | |
IntervalSet.add | interval | O((1 + merged) log runs) amortized |
IntervalSet.contains | interval | O(log runs) |
IntervalSet.contains_range | interval | O(log runs) |
IntervalSet.covered | interval | O(1) |
IntervalSet.each | interval | O(1) per run |
IntervalSet.new | interval | O(1) |
IntervalSet.next_covered | interval | O(log runs) |
IntervalSet.next_gap | interval | O(log runs) |
IntervalSet.remove | interval | O((1 + split) log runs) amortized |
IntervalSet.run_at | interval | O(log runs) |
IntervalSet.runs | interval | O(1) |
io | io | |
Items | seq | |
Items.src | seq | O(1) |
JumpTree | tree | |
JumpTree.add | tree | O(1) |
JumpTree.ancestor | tree | O(log n) |
JumpTree.depth | tree | O(1) |
JumpTree.dist | tree | O(log n) |
JumpTree.jump | tree | O(log n) |
JumpTree.jump_while | tree | O(log n) calls of pred |
JumpTree.lca | tree | O(log n) |
JumpTree.new | tree | O(n) |
JumpTree.parent | tree | O(1) |
JumpTree.root_of | tree | O(log n) |
Keys | seq | |
KmpAutomaton | strings | |
KmpAutomaton.find_all | strings | O(|text|) |
KmpAutomaton.len | strings | O(1) |
KmpAutomaton.link | strings | O(1) |
KmpAutomaton.new | strings | O(|pat| * |A|) |
KmpAutomaton.step | strings | O(1) |
KruskalTree | tree | |
KruskalTree.bottleneck | tree | O(log n) |
KruskalTree.reach | tree | O(log n) |
KruskalTree.top | tree | O(log n) calls of ok |
KruskalTree.tree | tree | O(1); built with the tree |
KruskalTree.up | tree | O(n) calls of op and leaf |
Layers | tree | |
Layers.below | tree | O(log n) |
Layers.level | tree | O(1) |
Layers.pos | tree | O(1) |
LazyEulerTourTree | tree | |
LazyEulerTourTree.apply_sub | tree | expected O(log n) |
LazyEulerTourTree.apply_tree | tree | expected O(log n) |
LazyEulerTourTree.connected | tree | expected O(log n) |
LazyEulerTourTree.cut | tree | expected O(log n) |
LazyEulerTourTree.fold_sub | tree | expected O(log n) |
LazyEulerTourTree.fold_tree | tree | expected O(log n) |
LazyEulerTourTree.get | tree | expected O(log n) |
LazyEulerTourTree.len | tree | expected O(log n) |
LazyEulerTourTree.link | tree | expected O(log n) |
LazyEulerTourTree.new | tree | O(n) |
LazyEulerTourTree.set | tree | expected O(log n) |
LazyLinkCut | tree | |
LazyLinkCut.access | tree | |
LazyLinkCut.apply_path | tree | amortized O(log n) |
LazyLinkCut.connected | tree | amortized O(log n) |
LazyLinkCut.cut | tree | amortized O(log n) |
LazyLinkCut.dist | tree | amortized O(log n) |
LazyLinkCut.fold_path | tree | amortized O(log n) |
LazyLinkCut.get | tree | amortized O(log n) |
LazyLinkCut.jump | tree | amortized O(log n) |
LazyLinkCut.lca | tree | amortized O(log n) |
LazyLinkCut.link | tree | amortized O(log n), with one root_of to check the trees differ |
LazyLinkCut.make_root | tree | amortized O(log n) |
LazyLinkCut.new | tree | O(n) |
LazyLinkCut.pull | tree | |
LazyLinkCut.push | tree | |
LazyLinkCut.put | tree | |
LazyLinkCut.root_of | tree | amortized O(log n) |
LazyLinkCut.rotate | tree | |
LazyLinkCut.set | tree | amortized O(log n) |
LazyLinkCut.splay | tree | |
LazyLinkCut.top | tree | |
LazyLinkCut.turn | tree | |
LazyTreap | lazy | |
LazyTreap.append | lazy | O(log n) expected |
LazyTreap.apply | lazy | O(log n) expected |
LazyTreap.apply_all | lazy | O(1) |
LazyTreap.apply_range | lazy | O(log n) expected |
LazyTreap.copy_from | lazy | |
LazyTreap.down | lazy | |
LazyTreap.erase_at | lazy | O(log n) expected |
LazyTreap.erase_range | lazy | O(log n) expected |
LazyTreap.get | lazy | O(log n) expected |
LazyTreap.ins | lazy | |
LazyTreap.insert | lazy | O(log n) expected |
LazyTreap.insert_at | lazy | O(log n) expected |
LazyTreap.is_empty | lazy | O(1) |
LazyTreap.len | lazy | O(1) |
LazyTreap.merge | lazy | |
LazyTreap.new | lazy | O(1) |
LazyTreap.priority | lazy | |
LazyTreap.pull | lazy | |
LazyTreap.push | lazy | O(log n) expected |
LazyTreap.put | lazy | |
LazyTreap.reserve | lazy | O(n) when it grows, else O(1) |
LazyTreap.reverse | lazy | O(log n) expected |
LazyTreap.split_at | lazy | O(log n) expected |
LazyTreap.split_pos | lazy | |
LazyTreap.split_val | lazy | |
LazyTreap.sz_of | lazy | |
LazyTreap.take | lazy | O(k + log n) |
LazyTreap.to_list | lazy | O(n) |
LazyTreap.walk | lazy | |
LcaTable | tree | |
LcaTable.dist | tree | O(1) |
LcaTable.lca | tree | O(1) |
LcaTable.new | tree | O(n log n) time and memory |
LiChao | dp | |
LiChao.add | dp | O(log n) for a whole line, O(log^2 n) on a segment, for n = over.len; at most one new cell per level |
LiChao.at | dp | O(log n) for n = over.len |
LiChao.clear | dp | O(1) amortized |
LiChao.kid | dp | |
LiChao.line_at | dp | O(log n) for n = over.len |
LiChao.new | dp | O(1) |
LiChao.settle | dp | |
LiChao.wins | dp | |
Lift | tree | |
Lift.ancestor | tree | O(log n) |
Lift.climb | tree | O(log n) calls of ok |
Lift.climb_while | tree | O(log n) calls of ok and op |
Lift.depth | tree | O(1) |
Lift.fold | tree | O(log n) calls of op |
Lift.lca | tree | O(log n) |
Lift.new | tree | O(n log n) time and memory |
Lift.of | tree | O(n log n) time and memory, n calls of next |
Lift.parent | tree | O(1) |
Line | dp | |
Line.at | dp | O(1) |
LinearRmq | sparse | |
LinearRmq.argbest | sparse | O(1) |
LinearRmq.best | sparse | O(1) |
LinearRmq.better | sparse | |
LinearRmq.in_block | sparse | |
LinearRmq.new | sparse | O(|D|) time and memory |
LinearRmq.try_best | sparse | O(1) |
LineContainer | dp | |
LineContainer.add | dp | O(log n) amortized |
LineContainer.at | dp | O(log n) |
LineContainer.best | dp | |
LineContainer.drop_end | dp | |
LineContainer.end | dp | |
LineContainer.floor_div | dp | |
LineContainer.len | dp | O(1) |
LineContainer.line_at | dp | O(log n) |
LineContainer.meet | dp | |
LineContainer.merge | dp | |
LineContainer.sign | dp | |
LineContainer.split | dp | |
LinkCut | tree | |
LinkCut.access | tree | |
LinkCut.connected | tree | amortized O(log n) |
LinkCut.cut | tree | amortized O(log n) |
LinkCut.dist | tree | amortized O(log n) |
LinkCut.fold_path | tree | amortized O(log n) |
LinkCut.get | tree | O(1) |
LinkCut.jump | tree | amortized O(log n) |
LinkCut.lca | tree | amortized O(log n) |
LinkCut.link | tree | amortized O(log n), with one root_of to check the trees differ |
LinkCut.make_root | tree | amortized O(log n) |
LinkCut.new | tree | O(n) |
LinkCut.pull | tree | |
LinkCut.push | tree | |
LinkCut.root_of | tree | amortized O(log n) |
LinkCut.rotate | tree | |
LinkCut.set | tree | amortized O(log n) |
LinkCut.splay | tree | |
LinkCut.top | tree | |
LinkCut.turn | tree | |
LinkedList | deque | |
LinkedList.bwd | deque | |
LinkedList.clear | deque | O(1) |
LinkedList.each | deque | O(1) per step |
LinkedList.each_rev | deque | O(1) per step |
LinkedList.first | deque | O(1) |
LinkedList.from_list | deque | O(n) |
LinkedList.fwd | deque | |
LinkedList.is_empty | deque | O(1) |
LinkedList.last | deque | O(1) |
LinkedList.len | deque | O(1) |
LinkedList.new | deque | O(1) |
LinkedList.node | deque | |
LinkedList.of | deque | O(1) |
LinkedList.pop | deque | O(1) |
LinkedList.pop_front | deque | O(1) |
LinkedList.push | deque | O(1) |
LinkedList.push_front | deque | O(1) |
LinkedList.reverse | deque | O(1) |
LinkedList.set_bwd | deque | |
LinkedList.set_fwd | deque | |
LinkedList.splice_back | deque | O(1) |
LinkedList.splice_front | deque | O(1) |
Lit | graph | |
Lit.flip | graph | O(1) |
Location | geometry | |
LongPaths | tree | |
LongPaths.slot | tree | O(1) |
LongPaths.slots | tree | O(1) |
Mapped | seq | |
Mapped.src | seq | O(1) |
Mark | dsu | |
MarkMap | marks | |
MarkMap.clear | marks | O(1) amortized; O(|D|) on the call that wraps the counter |
MarkMap.contains | marks | O(1) |
MarkMap.get | marks | O(1) |
MarkMap.is_empty | marks | O(1) |
MarkMap.len | marks | O(1) |
MarkMap.new | marks | O(|D|) |
MarkMap.remove | marks | O(1) |
MarkMap.set | marks | O(1) |
Marks | marks | |
Marks.add | marks | O(1) |
Marks.clear | marks | O(1) amortized; O(|D|) on the call that wraps the counter |
Marks.contains | marks | O(1) |
Marks.is_empty | marks | O(1) |
Marks.len | marks | O(1) |
Marks.new | marks | O(|D|) |
Marks.remove | marks | O(1) |
Mat | matrix | |
Mat.adjugate | matrix | O(n^3) time, O(n^2) space |
Mat.at | matrix | O(1) |
Mat.char_poly | matrix | O(n^3) time, O(n^2) space |
Mat.det | matrix | O(n^3) time, O(n^2) space |
Mat.det_mod | matrix | O(n^3 log m) |
Mat.filled | matrix | O(rows * cols) time and space |
Mat.from_flat | matrix | O(rows * cols) time and space |
Mat.from_rows | matrix | O(rows * cols) time and space |
Mat.get | matrix | O(1) |
Mat.identity | matrix | O(n^2) time and space |
Mat.inverse | matrix | O(n^3) time, O(n^2) space |
Mat.mul_vec | matrix | O(rows * cols) time, O(rows) space |
Mat.new | matrix | O(rows * cols) time and space |
Mat.pfaffian | matrix | O(n^3) time, O(n^2) space |
Mat.product | matrix | O(n^2) time and space (for the identity) |
Mat.rank | matrix | O(rows * cols * min(rows, cols)) time, O(rows * cols) space |
Mat.rref | matrix | O(rows * cols * min(rows, cols)) time, O(rows * cols) space |
Mat.set | matrix | O(1) |
Mat.solve | matrix | O(rows * cols * min(rows, cols)) time, O(rows * cols) space |
Mat.solve_space | matrix | O(rows * cols * min(rows, cols)) time, O(rows * cols) space |
Mat.transpose | matrix | O(rows * cols) time and space |
Mat.zeros | matrix | O(rows * cols) time and space |
Mat<T>.add | matrix | |
Mat<T>.mul | matrix | |
Mat<T>.pow | matrix | |
Mat<T>.sub | matrix | |
Matching | flow | |
Matching.add | flow | O(1) amortized |
Matching.augment | flow | O(V + E) |
Matching.augment_all | flow | O(E sqrt V) |
Matching.back | flow | O(1) |
Matching.cover | flow | O(V + E) |
Matching.len | flow | O(1) |
Matching.mate | flow | O(1) |
Matching.new | flow | O(L + R) |
Matching.remove | flow | O(V + E) |
MatPow | matrix | |
MatPow.apply_pow | matrix | O(n^2 log e) time, O(n) space |
MatPow.new | matrix | O(n^3 log max_exp) time, O(n^2 log max_exp) space |
Matroid | flow | |
Matroid.can_add | flow | |
Matroid.can_swap | flow | |
Matroid.rebuild | flow | |
MaxCount | algebra | |
MaxCount.join | algebra | O(1) |
MaxCount.monoid | algebra | O(1) |
MaxCount.of | algebra | O(1) |
MaxHeap | heap | |
MaxHeap.clear | heap | O(1) |
MaxHeap.drain | heap | O(n log n) |
MaxHeap.is_empty | heap | O(1) |
MaxHeap.len | heap | O(1) |
MaxHeap.new | heap | O(1) |
MaxHeap.of | heap | O(n) |
MaxHeap.peek | heap | O(1) |
MaxHeap.pop | heap | O(log n) |
MaxHeap.push | heap | O(log n) |
MaxHeap.push_all | heap | O(n + k log(n + k)) |
MaxHeap.push_pop | heap | O(log n); O(1) when x is returned |
MaxHeap.replace_top | heap | O(log n) |
MaxHeap.reserve | heap | O(cap) when the storage grows, O(1) otherwise |
MaxHeap.take | heap | O(1) |
MaxSub | algebra | |
MaxSub.add | algebra | |
MaxSub.empty | algebra | O(1) |
MaxSub.join | algebra | O(1) |
MaxSub.monoid | algebra | O(1) |
MaxSub.mul | algebra | |
MaxSub.of | algebra | O(1) |
MaxSub.rev | algebra | |
MaxSub.scale | algebra | O(1) |
MaxSub.try_best | algebra | O(1) |
MeldHeap | heap | |
MeldHeap.absorb | heap | O(log n) |
MeldHeap.add_all | heap | O(1) |
MeldHeap.clear | heap | O(1) |
MeldHeap.drain | heap | O(n log n) |
MeldHeap.is_empty | heap | O(1) |
MeldHeap.len | heap | O(1) |
MeldHeap.less | heap | |
MeldHeap.meld | heap | O(log n) |
MeldHeap.merge | heap | |
MeldHeap.new | heap | O(1) |
MeldHeap.node | heap | |
MeldHeap.of | heap | O(n) |
MeldHeap.peek | heap | O(1) |
MeldHeap.pop | heap | O(log n) |
MeldHeap.push | heap | O(log n) |
MeldHeap.push_all | heap | O(k log n) for k items |
MeldHeap.push_down | heap | |
MeldHeap.rank_of | heap | |
MeldHeap.take | heap | O(1) |
MeldHeap.top | heap | O(1) |
MergeSeg | segtree | |
MergeSeg.first_alive | segtree | O(log |D|) amortized |
MergeSeg.merge | segtree | O(log |D|) amortized per node absorbed |
MergeSeg.pop_min | segtree | |
MergeSeg.push_raw | segtree | |
MergeSeg.singleton | segtree | O(log |D|) |
MergeSortTree | segtree | |
MergeSortTree.count_ge | segtree | O(log^2 |D|) |
MergeSortTree.count_gt | segtree | O(log^2 |D|) |
MergeSortTree.count_in | segtree | O(log^2 |D|) |
MergeSortTree.count_le | segtree | O(log^2 |D|) |
MergeSortTree.count_lt | segtree | O(log^2 |D|) |
MergeSortTree.first_ge | segtree | O(log^2 |D|) |
MergeSortTree.last_le | segtree | O(log^2 |D|) |
MergeSortTree.lower_idx | segtree | |
MergeSortTree.new | segtree | O(|D| log |D|) time and memory |
MergeSortTree.upper_idx | segtree | |
MinCount | algebra | |
MinCount.join | algebra | O(1) |
MinCount.monoid | algebra | O(1) |
MinCount.of | algebra | O(1) |
MinMaxHeap | heap | |
MinMaxHeap.bubble_up | heap | |
MinMaxHeap.clear | heap | O(1) |
MinMaxHeap.first | heap | O(1) |
MinMaxHeap.is_empty | heap | O(1) |
MinMaxHeap.last | heap | O(1) |
MinMaxHeap.len | heap | O(1) |
MinMaxHeap.less | heap | |
MinMaxHeap.max_at | heap | |
MinMaxHeap.new | heap | O(1) |
MinMaxHeap.of | heap | O(n) |
MinMaxHeap.pop_first | heap | O(log n) |
MinMaxHeap.pop_last | heap | O(log n) |
MinMaxHeap.push | heap | O(log n), amortized over list growth |
MinMaxHeap.remove_at | heap | |
MinMaxHeap.reserve | heap | O(cap) when the storage grows, O(1) otherwise |
MinMaxHeap.swap | heap | |
MinMaxHeap.take | heap | O(1) |
MinMaxHeap.trickle_down | heap | |
Mod | mod | |
Mod.from_int | mod | O(1) |
Mod.inv | mod | O(log P) |
Mod.inv_all | mod | O(n + log P) |
Mod.log | mod | O(sqrt P) |
Mod.new | mod | O(1) |
Mod.sqrt | mod | O(log^2 P) |
Mod.try_inv | mod | O(log P) |
Mod<P>.add | mod | |
Mod<P>.div | mod | |
Mod<P>.mul | mod | |
Mod<P>.neg | mod | |
Mod<P>.pow | mod | |
Mod<P>.read | mod | |
Mod<P>.show | mod | |
Mod<P>.sub | mod | |
ModComb | mod | |
ModComb.choose | mod | O(omega(m) log n) |
ModComb.new | mod | O(sum p_i^e_i) |
MongePath | dp | |
MongePath.len | dp | O(1) |
MongePath.next | dp | O(1) amortized calls of cost |
MongePath.setup | dp | |
MongePath.val | dp | O(1) |
MongePath.w | dp | |
Monoid | algebra | |
Monoid.of | algebra | O(1) |
MonoStack | seq | |
MonoStack.clear | seq | O(1) |
MonoStack.is_empty | seq | O(1) |
MonoStack.len | seq | O(1) |
MonoStack.mark | seq | O(1) |
MonoStack.pops | seq | |
MonoStack.push | seq | O(1) amortized |
MonoStack.top | seq | O(1) |
MonoStack.undo_to | seq | O(1) amortized per undone push |
MonotoneHull | dp | |
MonotoneHull.add | dp | O(1) amortized |
MonotoneHull.at | dp | O(log n) |
MonotoneHull.at_next | dp | O(1) amortized |
MonotoneHull.best_next | dp | O(1) amortized |
MonotoneHull.clear | dp | O(1) |
MonotoneHull.covered | dp | |
MonotoneHull.len | dp | O(1) |
MonotoneHull.pop_line | dp | |
MonotoneHull.sign | dp | |
MonotoneHull.val_at | dp | |
Next | graph | |
Next.out | graph | O(1) per arc yielded |
OnlineHull | geometry | |
OnlineHull.add | geometry | O(log n) amortized |
OnlineHull.area2 | geometry | O(1) |
OnlineHull.clear | geometry | O(n) |
OnlineHull.extreme | geometry | O(log n) |
OnlineHull.is_empty | geometry | O(1) |
OnlineHull.iter | geometry | O(n) |
OnlineHull.len | geometry | O(1) |
OnlineHull.locate | geometry | O(log n) |
OnlineHull.new | geometry | O(1) |
OnlineHull.vertices | geometry | O(n) time and memory |
OnlineLis | seq | |
OnlineLis.clear | seq | O(1) |
OnlineLis.is_empty | seq | O(1) |
OnlineLis.len | seq | O(1) |
OnlineLis.mark | seq | O(1) |
OnlineLis.push | seq | O(log n) |
OnlineLis.reconstruct | seq | O(n), O(n) memory |
OnlineLis.undo_to | seq | O(1) amortized per undone push |
Only | graph | |
Only.deg | graph | O(deg u in g) |
Only.out | graph | O(1) to make, O(1) per arc of g walked |
Only.transpose | graph | O(n + m) |
Op | algebra | |
Op.op | algebra | |
Ordering | algebra | |
Pair | pair | |
Pair.at | pair | O(1) |
Pair.new | pair | O(1) |
Pair.other | pair | O(1) |
Palindromes | strings | |
Palindromes.count | strings | O(n) |
Palindromes.is_empty | strings | O(1) |
Palindromes.is_palindrome | strings | O(1) |
Palindromes.len | strings | O(1) |
Palindromes.longest | strings | O(n) |
Palindromes.longest_at | strings | |
Palindromes.longest_between | strings | |
PalindromicTree | strings | |
PalindromicTree.at | strings | |
PalindromicTree.contains | strings | O(|word|) |
PalindromicTree.diff | strings | |
PalindromicTree.distinct | strings | O(1) |
PalindromicTree.grow | strings | |
PalindromicTree.last_state | strings | O(1) |
PalindromicTree.len | strings | O(1) |
PalindromicTree.link | strings | |
PalindromicTree.min_palindrome_partition | strings | O(n log n) |
PalindromicTree.new | strings | O(|A|) |
PalindromicTree.occ_counts | strings | |
PalindromicTree.of | strings | O(|s| * |A|) memory, O(|s|) amortized time |
PalindromicTree.pal_len | strings | |
PalindromicTree.pop | strings | O(1) amortized |
PalindromicTree.push | strings | |
PalindromicTree.push_front | strings | O(1) amortized |
PalindromicTree.series_link | strings | |
PalindromicTree.size | strings | |
PalindromicTree.step | strings | |
ParityDsu | dsu | |
ParityDsu.consistent | dsu | O(1) |
ParityDsu.diff | dsu | O(log n) |
ParityDsu.find | dsu | O(log n) |
ParityDsu.mark | dsu | O(1) |
ParityDsu.new | dsu | O(n); three [V] arrays |
ParityDsu.same | dsu | O(log n) |
ParityDsu.size | dsu | O(log n) |
ParityDsu.undo_to | dsu | O(1) per undone unite |
ParityDsu.unite | dsu | O(log n), plus one log entry when it merges or contradicts |
ParityDsu<V>.mark | window | |
ParityDsu<V>.undo_to | window | |
Paths | graph | |
Paths.arcs | graph | O(path length) |
Paths.get | graph | O(1) dense, O(1) expected hashed |
Paths.iter | graph | O(1) to make, O(1) per item |
Paths.path | graph | O(path length) |
Paths.reached | graph | O(1) |
Paths.tight | graph | O(n + m) |
PermKind | tree | |
PermNode | tree | |
PermTree | tree | |
PermTree.leaf | tree | O(1) |
PermTree.left | tree | O(1) |
PermTree.new | tree | O(n) |
PermTree.node | tree | O(1) |
PermTree.right | tree | O(1) |
PermTree.span | tree | O(1) |
PermTree.vals | tree | O(1) |
PersistentArray | persistent | |
PersistentArray.base | persistent | O(1) |
PersistentArray.build_list | persistent | |
PersistentArray.get | persistent | O(log n) |
PersistentArray.new | persistent | O(n) time and memory for n = |D| |
PersistentArray.push_node | persistent | |
PersistentArray.set | persistent | O(log n) time and memory |
PersistentArray.set_rec | persistent | |
PersistentDsu | dsu | |
PersistentDsu.base | dsu | O(1) |
PersistentDsu.build | dsu | |
PersistentDsu.find | dsu | O(log² n) |
PersistentDsu.get | dsu | |
PersistentDsu.new | dsu | O(n) |
PersistentDsu.put | dsu | |
PersistentDsu.reserve | dsu | O(nodes) |
PersistentDsu.root_ord | dsu | |
PersistentDsu.same | dsu | O(log² n) |
PersistentDsu.size | dsu | O(log² n) |
PersistentDsu.unite | dsu | O(log² n) time and O(log n) memory |
PersistentLazySegTree | persistent | |
PersistentLazySegTree.all | persistent | O(1) |
PersistentLazySegTree.apply | persistent | O(log n) time and memory |
PersistentLazySegTree.apply_rec | persistent | |
PersistentLazySegTree.base | persistent | O(1) |
PersistentLazySegTree.build_list | persistent | |
PersistentLazySegTree.fold | persistent | O(log n) |
PersistentLazySegTree.fold_rec | persistent | |
PersistentLazySegTree.get | persistent | O(log n) |
PersistentLazySegTree.new | persistent | O(n) time and memory with a: or fill:, O(1) otherwise, for n = |D| |
PersistentLazySegTree.push_node | persistent | |
PersistentLazySegTree.set | persistent | O(log n) time and memory |
PersistentLazySegTree.set_rec | persistent | |
PersistentLazySegTree.tagged | persistent | |
PersistentSegTree | persistent | |
PersistentSegTree.all | persistent | O(1) |
PersistentSegTree.base | persistent | O(1) |
PersistentSegTree.build_list | persistent | |
PersistentSegTree.diff_kth | persistent | O(log n) |
PersistentSegTree.fold | persistent | O(log n) |
PersistentSegTree.fold_rec | persistent | |
PersistentSegTree.get | persistent | O(log n) |
PersistentSegTree.left_while | persistent | O(log n) calls of ok |
PersistentSegTree.lw | persistent | |
PersistentSegTree.new | persistent | O(n) time and memory with a: or fill:, O(1) otherwise, for n = |D| |
PersistentSegTree.push_node | persistent | |
PersistentSegTree.reserve | persistent | O(nodes) |
PersistentSegTree.right_while | persistent | O(log n) calls of ok |
PersistentSegTree.rw | persistent | |
PersistentSegTree.set | persistent | O(log n) time and memory |
PersistentSegTree.set_rec | persistent | |
PersistentSegTree.update | persistent | O(log n) time and memory, one call of f |
PersistentSegTree.update_rec | persistent | |
Plane3 | geometry | |
Plane3.dist | geometry | O(1) |
Plane3.project | geometry | O(1) |
Plane3.through | geometry | O(1) |
PMultiset | persistent | |
PMultiset.cmp | persistent | O(log |D|) |
PMultiset.count | persistent | O(log |D|) |
PMultiset.empty | persistent | O(1) |
PMultiset.with | persistent | O(log |D|) time and memory |
PMultiset.without | persistent | O(log |D|) time and memory |
Poly | poly | |
Poly.at | poly | O(1) |
Poly.deg | poly | O(1) plus the number of stored trailing zeros |
Poly.deriv | poly | O(n) |
Poly.eval | poly | O(n) |
Poly.exp | poly | O(n log n) |
Poly.from_int | poly | O(1) |
Poly.integral | poly | O(n) |
Poly.inv | poly | O(n log n) |
Poly.is_zero | poly | O(1) plus the number of stored trailing zeros |
Poly.len | poly | O(1) |
Poly.log | poly | O(n log n) |
Poly.new | poly | O(n) |
Poly.one | poly | O(1) |
Poly.pow | poly | O(n log n) |
Poly.set | poly | O(1), or O(i) when it grows |
Poly.shift | poly | O(n log n) |
Poly.sqrt | poly | O(n log n + log^2 P) |
Poly.transposed_mul | poly | O((n + m) log(n + m)) |
Poly.truncated | poly | O(n) |
Poly.x | poly | O(1) |
Poly.zero | poly | O(1) |
Poly<T>.add | poly | |
Poly<T>.div | poly | |
Poly<T>.mul | poly | |
Poly<T>.neg | poly | |
Poly<T>.sub | poly | |
PotentialDsu | dsu | |
PotentialDsu.components | dsu | O(1) |
PotentialDsu.consistent | dsu | O(1) |
PotentialDsu.diff | dsu | O(log n) |
PotentialDsu.find | dsu | O(log n) |
PotentialDsu.mark | dsu | O(1) |
PotentialDsu.new | dsu | O(n); three [V] arrays |
PotentialDsu.same | dsu | O(log n) |
PotentialDsu.size | dsu | O(log n) |
PotentialDsu.undo_to | dsu | O(1) per undone unite |
PotentialDsu.unite | dsu | O(log n), plus one log entry when it merges or contradicts |
PotentialDsu<V>.mark | window | |
PotentialDsu<V>.undo_to | window | |
PreferredPaths | tree | |
PreferredPaths.access | tree | amortized O(log n) switches |
PreferredPaths.new | tree | O(n) |
Prefix | prefix | |
Prefix.all | prefix | O(1) |
Prefix.cyclic_sum | prefix | O(1) |
Prefix.filling | prefix | O(|D|) time and space |
Prefix.first_ge | prefix | O(log |D|) |
Prefix.first_gt | prefix | O(log |D|) |
Prefix.fold | prefix | O(1) |
Prefix.get | prefix | O(1) |
Prefix.new | prefix | O(|D|) time and space |
Prefix.of_cuts | prefix | |
Prefix.prefix | prefix | O(1) |
Prefix.suffix | prefix | O(1) |
PrefixXorBasis | matrix | |
PrefixXorBasis.contains | matrix | O(62) |
PrefixXorBasis.max_xor | matrix | O(62) |
PrefixXorBasis.new | matrix | O(1) |
PrefixXorBasis.push | matrix | O(62) time and space |
PrefixXorBasis.rank | matrix | O(62) |
PrimePowerComb | mod | |
PrimePowerComb.choose | mod | O(log_p n) |
PrimePowerComb.free_fact | mod | |
PrimePowerComb.new | mod | O(p^e) time and memory |
PrimePowerComb.p_count | mod | |
Pt | geometry | |
Pt.add | geometry | |
Pt.angle | geometry | O(1) |
Pt.chebyshev | geometry | O(1) |
Pt.cross | geometry | O(1) |
Pt.cross128 | geometry | O(1) |
Pt.dist | geometry | O(1) |
Pt.dist2 | geometry | O(1) |
Pt.dist2_128 | geometry | O(1) |
Pt.dot | geometry | O(1) |
Pt.dot128 | geometry | O(1) |
Pt.len | geometry | O(1) |
Pt.manhattan | geometry | O(1) |
Pt.mul | geometry | |
Pt.neg | geometry | |
Pt.norm2 | geometry | O(1) |
Pt.norm2_128 | geometry | O(1) |
Pt.perp | geometry | O(1) |
Pt.perp_cw | geometry | O(1) |
Pt.show | geometry | |
Pt.sub | geometry | |
Pt.to_vec | geometry | O(1) |
Pt.unit_dir | geometry | O(log max(|x|, |y|)) |
Pt3 | geometry | |
Pt3.add | geometry | |
Pt3.chebyshev | geometry | O(1) |
Pt3.cross | geometry | O(1) |
Pt3.dist | geometry | O(1) |
Pt3.dist2 | geometry | O(1) |
Pt3.dot | geometry | O(1) |
Pt3.dot128 | geometry | O(1) |
Pt3.len | geometry | O(1) |
Pt3.manhattan | geometry | O(1) |
Pt3.mul | geometry | |
Pt3.neg | geometry | |
Pt3.norm2 | geometry | O(1) |
Pt3.norm2_128 | geometry | O(1) |
Pt3.show | geometry | |
Pt3.sub | geometry | |
Pt3.to_vec3 | geometry | O(1) |
RangeKth | persistent | |
RangeKth.count_in | persistent | O(log n) |
RangeKth.count_le | persistent | O(log n) |
RangeKth.count_lt | persistent | O(log n) |
RangeKth.count_prefix | persistent | |
RangeKth.inc | persistent | |
RangeKth.kth | persistent | O(log n) |
RangeKth.lower_val | persistent | |
RangeKth.new | persistent | O(n log n) time and memory for n = a.len |
RangeKth.upper_val | persistent | |
Ratio | math | |
Ratio.abs | math | O(1) |
Ratio.add | math | |
Ratio.ceil | math | O(1) |
Ratio.div | math | |
Ratio.floor | math | O(1) |
Ratio.from_int | math | O(1) |
Ratio.inv | math | O(1) |
Ratio.lt | math | |
Ratio.mul | math | |
Ratio.neg | math | |
Ratio.new | math | O(log min(|p|, |q|)) |
Ratio.show | math | |
Ratio.sub | math | |
Rebased | seq | |
Rect | geometry | |
Rect.area | geometry | O(1) |
Rect.contains | geometry | O(1) |
Rect.intersect | geometry | O(1) |
Rect.is_empty | geometry | O(1) |
RelaxedConvolve | ntt | |
RelaxedConvolve.new | ntt | O(1) |
RelaxedConvolve.push | ntt | O(log^2 k) amortized |
Rev | seq | |
Rev.src | seq | O(1) |
Reversible | algebra | |
Reversible.rev | algebra | |
Reweighted | graph | |
Ring | seq | |
Ring.from | seq | O(1) per step |
Ring.maximal | seq | O(n) pushes and pops on state |
Ring.minimal | seq | O(n) pushes and pops on state |
Ring.next | seq | O(1) |
Ring.prev | seq | O(1) |
Ring.span | seq | O(1) |
Ring.step | seq | O(1) |
Ring.windows | seq | O(1) per window |
RingRange | seq | |
RingRange.contains | seq | O(1) |
RingRange.end | seq | O(1) |
RingRange.keys | seq | O(1) to make, O(1) per step |
RingRange.len | seq | O(1) |
RingRange.start | seq | O(1) |
RingSlice | seq | |
RingSlice.end | seq | O(1) |
RingSlice.keys | seq | O(1) to make, O(1) per step |
RingSlice.len | seq | O(1) |
RingSlice.range | seq | O(1) |
RingSlice.start | seq | O(1) |
Rng | rand | |
Rng.chance | rand | O(1) |
Rng.float | rand | O(1) |
Rng.int | rand | O(1) |
Rng.new | rand | O(1) |
Rng.next | rand | O(1) |
Rng.perm | rand | O(n) |
Rng.pick | rand | O(1) |
Rng.sample | rand | O(|from|) |
Rng.shuffle | rand | O(n) |
RollbackArray | dsu | |
RollbackArray.get | dsu | O(1) |
RollbackArray.mark | dsu | O(1) |
RollbackArray.new | dsu | O(n) calls of init, for n = D.count |
RollbackArray.set | dsu | O(1), plus one log entry |
RollbackArray.undo_to | dsu | O(1) per undone set |
RollingHash | strings | |
RollingHash.all | strings | O(1) |
RollingHash.combine | strings | O(1) amortized (the power table grows past len on demand) |
RollingHash.concat | strings | O(|parts|) amortized |
RollingHash.eq_sub | strings | |
RollingHash.get | strings | O(1) |
RollingHash.hash_of | strings | O(|seq|) |
RollingHash.is_empty | strings | O(1) |
RollingHash.lcp | strings | O(log n) |
RollingHash.lcp_with | strings | O(log min(|self| - a, |other| - b)) |
RollingHash.lcs | strings | O(log n) |
RollingHash.len | strings | O(1) |
RollingHash.new | strings | |
RollingHash.pop | strings | O(1) |
RollingHash.push | strings | O(1) amortized |
RollingHash.raw_slice | strings | |
RollingHash.slice | strings | O(1) |
RollingHash61 | strings | |
RollingHash61.all | strings | O(1) |
RollingHash61.combine | strings | O(1) amortized (the power table grows past len on demand) |
RollingHash61.get | strings | O(1) |
RollingHash61.is_empty | strings | O(1) |
RollingHash61.lcp | strings | O(log n) |
RollingHash61.lcp_with | strings | O(log min(|self| - a, |other| - b)) |
RollingHash61.lcs | strings | O(log n) |
RollingHash61.len | strings | O(1) |
RollingHash61.new | strings | O(n) |
RollingHash61.pop | strings | O(1) |
RollingHash61.push | strings | O(1) amortized |
RollingHash61.slice61 | strings | |
Rooted | tree | |
Rooted.above | tree | O(n) calls of lift and finish, O(n) calls of op |
Rooted.ancestor | tree | O(log n) |
Rooted.ancestors | tree | O(1) per vertex, O(depth(v)) in all |
Rooted.apply_path | tree | O(log² n) |
Rooted.below | tree | O(1) |
Rooted.build | tree | |
Rooted.centroid | tree | O(depth) |
Rooted.centroids | tree | O(depth) |
Rooted.chain | tree | O(1) |
Rooted.chains | tree | O(log n) ranges |
Rooted.child_arcs | tree | O(1) per child |
Rooted.children | tree | O(1) to start, O(1) per child |
Rooted.depth | tree | O(1) |
Rooted.diameter | tree | O(n) |
Rooted.dist | tree | O(log n) |
Rooted.down | tree | O(n) calls of f |
Rooted.euler_tour | tree | O(1) per item |
Rooted.events | tree | O(n) |
Rooted.excl_fold | tree | O(k) calls of f and of op, O(k) memory |
Rooted.farthest | tree | O(log n): at most four dist calls |
Rooted.fold_path | tree | O(log² n) with one structure |
Rooted.forest | tree | O(n + m) |
Rooted.from_parents | tree | O(n) |
Rooted.is_anc | tree | O(1) |
Rooted.jump | tree | O(log n) |
Rooted.jump_while | tree | O(log² n) calls of pred |
Rooted.layers | tree | O(n) |
Rooted.lca | tree | O(log n) |
Rooted.light | tree | O(children) |
Rooted.long_paths | tree | O(n) |
Rooted.lower | tree | O(1) |
Rooted.meet | tree | O(log n) |
Rooted.new | tree | O(n + m) for m listed arcs, without recursion |
Rooted.on_path | tree | O(log n) |
Rooted.parent | tree | O(1) |
Rooted.path | tree | O(log n + |path|) |
Rooted.pos | tree | O(1) |
Rooted.preorder | tree | O(size(v)), less when pruned |
Rooted.reorder | tree | O(n) |
Rooted.reroot | tree | O(n) calls of lift and finish, O(n) calls of op |
Rooted.root_of | tree | O(log n) |
Rooted.roots | tree | O(1) to make, O(1) per root |
Rooted.shapes | tree | O(n log n) |
Rooted.size | tree | O(1) |
Rooted.sub | tree | O(1) |
Rooted.sub_at | tree | O(log n) |
Rooted.subtree | tree | O(size(v)) |
Rooted.subtree_sizes | tree | O(1); a view of the stored sizes |
Rooted.top | tree | O(1) |
Rooted.tour | tree | O(1) to make, O(n) to walk |
Rooted.try_from_parents | tree | O(n) |
Rooted.up | tree | O(n) calls of lift, op and finish |
Rooted.up_arc | tree | O(1) |
Rooted.virtual | tree | O(k log k + k log n) for k keys |
Rooted.w | tree | O(1) |
Rope | lazy | |
Rope.apply | lazy | O(log n) expected |
Rope.down | lazy | |
Rope.emit | lazy | |
Rope.find | lazy | |
Rope.get | lazy | O(log n) expected |
Rope.join | lazy | |
Rope.new | lazy | O(|D|) |
Rope.pull | lazy | |
Rope.reverse | lazy | O(log n) expected |
Rope.set | lazy | O(log n) expected |
Rope.size | lazy | |
Rope.split | lazy | |
Rope.tag_node | lazy | |
Rope.to_array | lazy | O(|D|) |
SegTree | segtree | |
SegTree.all | segtree | O(1) |
SegTree.apply | segtree | O(log |D|) |
SegTree.apply_all | segtree | O(1) amortized when the tags commute, else O(|D|) |
SegTree.at | segtree | O(log |D|) per write |
SegTree.build | segtree | |
SegTree.build_lazy | segtree | |
SegTree.clear | segtree | O(|D|) |
SegTree.fold | segtree | O(log |D|) |
SegTree.get | segtree | O(1); O(log |D|) on a tree with act: |
SegTree.left_while | segtree | O(log |D|) |
SegTree.monoid | segtree | O(1) |
SegTree.new | segtree | O(|D|); O(1) with over: |
SegTree.of | segtree | O(|D|), calling f once per position in key order |
SegTree.open | segtree | |
SegTree.pull | segtree | |
SegTree.pull_node | segtree | |
SegTree.push | segtree | |
SegTree.put | segtree | |
SegTree.refresh | segtree | O(log |D|) plus one call of f |
SegTree.right_while | segtree | O(log |D|) |
SegTree.set | segtree | O(log |D|) |
SegTree.try_fold | segtree | O(log |D|) |
SegTree.update | segtree | O(log |D|) plus one call of f |
SegTree.walk | segtree | O(log |D|) |
SegTree2D | segtree | |
SegTree2D.all | segtree | O(1) |
SegTree2D.fold | segtree | O(log |R| * log |C|) |
SegTree2D.fold_row | segtree | |
SegTree2D.get | segtree | O(1) |
SegTree2D.new | segtree | O(|R| * |C|) |
SegTree2D.set | segtree | O(log |R| * log |C|) |
SegTree2D.update | segtree | O(log |R| * log |C|) plus one call of f |
Selective | algebra | |
Semigroup | algebra | |
SemiRelaxedConvolve | ntt | |
SemiRelaxedConvolve.new | ntt | O(b.len) |
SemiRelaxedConvolve.push | ntt | O(log^2 k) amortized |
Semiring | algebra | |
Settle | heap | |
Settle.better | heap | |
Settle.get | heap | O(1) expected |
Settle.offer | heap | O(log n) amortized, n the offers so far |
Settle.pop | heap | O(log n) amortized, n the offers so far |
Settle.settled | heap | O(1) expected |
Settle.sift_down | heap | |
Settle.sift_up | heap | |
Sieve | math | |
Sieve.div_count_table | math | O(n) |
Sieve.div_sum_table | math | O(n) |
Sieve.divisors | math | O(log x) to start, O(1) per divisor |
Sieve.factor | math | O(log x) |
Sieve.is_prime | math | O(1) |
Sieve.mobius | math | O(log x) |
Sieve.mobius_table | math | O(n) |
Sieve.new | math | O(n) time and memory |
Sieve.phi | math | O(log x) |
Sieve.phi_table | math | O(n) |
Sign | math | |
Slice | seq | |
Slice.is_empty | seq | O(1) |
Slice.iter | seq | O(1) per step |
Slice.keys | seq | O(1) |
Slice.len | seq | O(1) |
SortedBag | bag | |
SortedBag.absorb | bag | O(min(n, m) log(n + m)) expected |
SortedBag.add | bag | O(log n) expected |
SortedBag.add_many | bag | O(log n) expected, independent of c |
SortedBag.add_unique | bag | |
SortedBag.clear | bag | O(1) |
SortedBag.contains | bag | O(log n) expected |
SortedBag.count | bag | O(log n) expected |
SortedBag.count_of | bag | O(1) |
SortedBag.cursor_at | bag | O(log n) expected |
SortedBag.cursor_first | bag | O(log n) expected |
SortedBag.cursor_ge | bag | O(log n) expected |
SortedBag.cursor_gt | bag | O(log n) expected |
SortedBag.cursor_last | bag | O(log n) expected |
SortedBag.cursor_le | bag | O(log n) expected |
SortedBag.cursor_lt | bag | O(log n) expected |
SortedBag.distinct | bag | O(1) |
SortedBag.drain | bag | O(k log n) expected for k removed elements |
SortedBag.drain_range | bag | O(log n + k) expected for k removed |
SortedBag.entries | bag | O(1) amortized per step |
SortedBag.entries_rev | bag | O(1) amortized per step |
SortedBag.erase_at | bag | |
SortedBag.first | bag | O(1) |
SortedBag.first_true | bag | O(log n) expected calls of ok |
SortedBag.hi_ok | bag | |
SortedBag.insert_at | bag | |
SortedBag.is_empty | bag | O(1) |
SortedBag.join | bag | O(log n) expected |
SortedBag.key_of | bag | O(1) |
SortedBag.last | bag | O(1) |
SortedBag.last_true | bag | O(log n) expected calls of ok |
SortedBag.len | bag | O(1) |
SortedBag.lo_ok | bag | |
SortedBag.make_node | bag | |
SortedBag.merge | bag | |
SortedBag.move_out | bag | |
SortedBag.new | bag | O(1) |
SortedBag.next_cursor | bag | O(1) amortized, O(log n) worst case |
SortedBag.nth | bag | O(log n) expected |
SortedBag.of | bag | O(n log n) expected |
SortedBag.pop_first | bag | O(log n) expected |
SortedBag.pop_last | bag | O(log n) expected |
SortedBag.prev_cursor | bag | O(1) amortized, O(log n) worst case |
SortedBag.pull | bag | |
SortedBag.range | bag | O(1) to make; see SortedRange for each query |
SortedBag.range_each | bag | |
SortedBag.range_each_rev | bag | |
SortedBag.range_first | bag | |
SortedBag.range_last | bag | |
SortedBag.range_len | bag | |
SortedBag.rank | bag | O(log n) expected |
SortedBag.rank_le | bag | |
SortedBag.refresh | bag | |
SortedBag.remove | bag | O(log n) expected |
SortedBag.remove_all | bag | O(log n) expected |
SortedBag.reserve | bag | O(cap) when the pool grows, O(1) otherwise |
SortedBag.split_at | bag | O(log n + s log n) expected, s the smaller side's distinct keys |
SortedBag.split_lt | bag | |
SortedBag.sub_of | bag | |
SortedBag.sum | bag | O(n) |
SortedBag.take | bag | O(1) |
SortedBag.take_first | bag | O(log n) expected |
SortedBag.to_list | bag | O(n) |
SortedMap | bag | |
SortedMap.absorb | bag | O(min(n, m) log(n + m)) expected |
SortedMap.at | bag | |
SortedMap.clear | bag | O(1) |
SortedMap.contains | bag | O(log n) expected |
SortedMap.drain | bag | O(k log n) expected for k removed entries |
SortedMap.each_rev | bag | O(1) amortized per step |
SortedMap.entry | bag | |
SortedMap.first | bag | O(1) |
SortedMap.first_ge | bag | O(log n) expected |
SortedMap.first_gt | bag | O(log n) expected |
SortedMap.first_true | bag | O(log n) expected calls of ok |
SortedMap.get | bag | O(log n) expected |
SortedMap.is_empty | bag | O(1) |
SortedMap.items | bag | O(1) to make, O(1) amortized per step |
SortedMap.join | bag | O(log n) expected |
SortedMap.keys | bag | O(1) to make, O(1) amortized per step |
SortedMap.last | bag | O(1) |
SortedMap.last_le | bag | O(log n) expected |
SortedMap.last_lt | bag | O(log n) expected |
SortedMap.last_true | bag | O(log n) expected calls of ok |
SortedMap.len | bag | O(1) |
SortedMap.new | bag | O(1) |
SortedMap.nth | bag | O(log n) expected |
SortedMap.pop_first | bag | O(log n) expected |
SortedMap.pop_last | bag | O(log n) expected |
SortedMap.rank | bag | O(log n) expected |
SortedMap.remove | bag | O(log n) expected |
SortedMap.reserve | bag | O(cap) when the pool grows, O(1) otherwise |
SortedMap.set | bag | O(log n) expected |
SortedMap.split_at | bag | O(log n) expected |
SortedMap.take | bag | O(1) |
SortedMap.values | bag | O(1) to make, O(1) amortized per step |
SortedRange | bag | |
SortedRange.each | bag | O(log n + k) expected for k keys visited |
SortedRange.first | bag | O(log n) expected |
SortedRange.is_empty | bag | O(log n) expected |
SortedRange.last | bag | O(log n) expected |
SortedRange.len | bag | O(log n) expected |
SortedRange.rev | bag | O(log n + k) expected for k keys visited |
SortedSet | bag | |
SortedSet.absorb | bag | O(min(n, m) log(n + m)) expected |
SortedSet.add | bag | O(log n) expected |
SortedSet.clear | bag | O(1) |
SortedSet.contains | bag | O(log n) expected |
SortedSet.drain | bag | O(k log n) expected for k removed keys |
SortedSet.each | bag | O(1) amortized per step |
SortedSet.each_rev | bag | O(1) amortized per step |
SortedSet.first | bag | O(1) |
SortedSet.first_true | bag | O(log n) expected calls of ok |
SortedSet.is_empty | bag | O(1) |
SortedSet.join | bag | O(log n) expected |
SortedSet.last | bag | O(1) |
SortedSet.last_true | bag | O(log n) expected calls of ok |
SortedSet.len | bag | O(1) |
SortedSet.new | bag | O(1) |
SortedSet.nth | bag | O(log n) expected |
SortedSet.of | bag | O(n log n) expected |
SortedSet.pop_first | bag | O(log n) expected |
SortedSet.pop_last | bag | O(log n) expected |
SortedSet.range | bag | O(1) to make; see SortedRange for each query |
SortedSet.range_each | bag | |
SortedSet.range_each_rev | bag | |
SortedSet.range_first | bag | |
SortedSet.range_last | bag | |
SortedSet.range_len | bag | |
SortedSet.rank | bag | O(log n) expected |
SortedSet.remove | bag | O(log n) expected |
SortedSet.reserve | bag | O(cap) when the pool grows, O(1) otherwise |
SortedSet.set | bag | O(log n) expected |
SortedSet.split_at | bag | O(log n + s log n) expected, s the smaller side's size |
SortedSet.sum | bag | O(log n) expected |
SortedSet.take | bag | O(1) |
SortedSet.to_list | bag | O(n) |
SosOver | ntt | |
SparseFenwick2D | fenwick | |
SparseFenwick2D.add | fenwick | O(log^2 n) |
SparseFenwick2D.add_point | fenwick | O(1) amortized |
SparseFenwick2D.build | fenwick | O(n log n) for n registered points; memory O(n log n) |
SparseFenwick2D.corner | fenwick | |
SparseFenwick2D.fold | fenwick | O(log^2 n) |
SparseFenwick2D.new | fenwick | O(1) |
SparseIntervalMap | interval | |
SparseIntervalMap.assign | interval | O((1 + removed) log runs) amortized |
SparseIntervalMap.each | interval | O(1) per run |
SparseIntervalMap.each_rev | interval | O(1) per run |
SparseIntervalMap.get | interval | O(log runs) |
SparseIntervalMap.merge_at | interval | |
SparseIntervalMap.new | interval | O(1) |
SparseIntervalMap.range | interval | O(log runs + k) for k pieces |
SparseIntervalMap.run_at | interval | O(log runs) |
SparseIntervalMap.runs | interval | O(1) |
SparseIntervalMap.split | interval | |
SparseIntervalMap.update | interval | O((1 + touched) log runs) |
SparseIntervalSet | interval | |
SparseIntervalSet.add | interval | O((1 + merged) log runs) amortized |
SparseIntervalSet.contains | interval | O(log runs) |
SparseIntervalSet.covered | interval | O(1) |
SparseIntervalSet.each | interval | O(1) per interval |
SparseIntervalSet.new | interval | O(1) |
SparseIntervalSet.next_gap | interval | O(log runs) |
SparseIntervalSet.remove | interval | O((1 + split) log runs) amortized |
SparseIntervalSet.runs | interval | O(1) |
SparseSet | marks | |
SparseSet.add | marks | O(1) |
SparseSet.clear | marks | O(1) |
SparseSet.contains | marks | O(1) |
SparseSet.each | marks | O(len) |
SparseSet.is_empty | marks | O(1) |
SparseSet.len | marks | O(1) |
SparseSet.new | marks | O(|D|) |
SparseSet.remove | marks | O(1) |
SparseTable | sparse | |
SparseTable.all | sparse | O(1) |
SparseTable.fold | sparse | O(1) |
SparseTable.get | sparse | O(1) |
SparseTable.new | sparse | O(|D| log |D|) time and memory, op called O(|D| log |D|) times |
SparseTable.try_fold | sparse | O(1) |
SparseTable2D | sparse | |
SparseTable2D.at | sparse | |
SparseTable2D.fold | sparse | O(1) |
SparseTable2D.get | sparse | O(1) |
SparseTable2D.new | sparse | O(|R| |C| log |R| log |C|) time and memory |
SparseTable2D.try_fold | sparse | O(1) |
Step | dp | |
Step.prune | dp | O(1) |
SubproductTree | poly | |
SubproductTree.eval | poly | O((deg f + m) log^2 m) |
SubproductTree.eval_transposed | poly | O(m log^2 m) |
SubproductTree.interpolate | poly | O(m log^2 m) |
SubproductTree.new | poly | O(m log^2 m) time, O(m log m) space |
SubseqStep | seq | |
SubseqStep.prune | seq | O(1) |
Subset | subset | |
Subset.complement | subset | O(1) |
Subset.contains | subset | O(1) |
Subset.empty | subset | O(1) |
Subset.first | subset | O(1) |
Subset.full | subset | O(1) |
Subset.items | subset | O(1) per member |
Subset.len | subset | O(1) |
Subset.set | subset | O(1) |
Subset.shifted | subset | O(1) |
Subset.single | subset | O(1) |
Subset.subsets | subset | O(1) per subset, 2^s.len subsets |
Subset.supersets | subset | O(1) per superset, 2^(|B| - s.len) supersets |
Subset.with | subset | O(1) |
Subset.without | subset | O(1) |
Subset<B>.bitand | subset | |
Subset<B>.bitor | subset | |
Subset<B>.bitxor | subset | |
Subset<B>.sub | subset | |
SuffixArray | strings | |
SuffixArray.arg_min | strings | |
SuffixArray.compare | strings | O(1) |
SuffixArray.count | strings | O(|pat| log n) |
SuffixArray.distinct | strings | O(n) |
SuffixArray.find_all | strings | O(|pat| log n + occurrences) |
SuffixArray.is_empty | strings | O(1) |
SuffixArray.kth_distinct | strings | O(log n) |
SuffixArray.lcp_between | strings | O(1) |
SuffixArray.lcp_of_ranks | strings | O(1) |
SuffixArray.lcp_range | strings | O(log n) |
SuffixArray.len | strings | O(1) |
SuffixArray.new | strings | O(n) for Str and small integer alphabets, O(n log n) otherwise |
SuffixArray.rank_range | strings | O(|pat| log n) |
SuffixArray.split | strings | O(1) |
SuffixAutomaton | strings | |
SuffixAutomaton.add_empty_state | strings | |
SuffixAutomaton.add_word | strings | O(|word|) amortized |
SuffixAutomaton.clone_state | strings | |
SuffixAutomaton.contains | strings | O(|word|) |
SuffixAutomaton.distinct | strings | O(states) |
SuffixAutomaton.endpos_tree | strings | O(states) |
SuffixAutomaton.find | strings | |
SuffixAutomaton.first_pos | strings | |
SuffixAutomaton.kth_substring | strings | O(states * |A|) |
SuffixAutomaton.lcs | strings | |
SuffixAutomaton.len | strings | O(1) |
SuffixAutomaton.link | strings | |
SuffixAutomaton.longest | strings | |
SuffixAutomaton.new | strings | O(|A|) |
SuffixAutomaton.occ_counts | strings | |
SuffixAutomaton.of | strings | O(|s| * |A|) memory, O(|s|) amortized time |
SuffixAutomaton.push | strings | |
SuffixAutomaton.reset | strings | O(1) |
SuffixAutomaton.root | strings | O(1) |
SuffixAutomaton.shortest | strings | |
SuffixAutomaton.states | strings | O(states) |
SuffixAutomaton.step | strings | |
SuffixAutomaton.topo_order | strings | |
SuffixTreeEdge | strings | |
Sweep | window | |
Sweep.move | window | O(|dl| + |dr|) pushes and pops, where dl and dr are the moves of the two ends |
Sweep.new | window | O(1), plus start.len pushes when start is given |
Sweep.range | window | O(1) |
SweepAdd | prefix | |
SweepAdd.add | prefix | O(1) |
SweepAdd.advance | prefix | O(1) |
SweepAdd.current | prefix | O(1) |
SweepAdd.new | prefix | O(|D|) time and space |
Target | graph | |
Target.to | graph | O(1) |
TimeStep | timetree | |
TimeTree | timetree | |
TimeTree.add_interval | timetree | O(log q) |
TimeTree.add_range | timetree | O(log q) |
TimeTree.emit_dfs | timetree | |
TimeTree.event | timetree | O(1) |
TimeTree.link | timetree | |
TimeTree.new | timetree | O(q) time and memory |
TimeTree.run | timetree | O(q + m log q) callback calls for m scheduled intervals, O(log q) extra stack |
TimeTree.run_node | timetree | |
TimeTree.steps | timetree | O(q + m log q) time and memory for m scheduled intervals |
TimeTree.walk | timetree | O(1) amortized per step, O(log q) extra stack |
Track | window | |
Track.pop | window | |
Track.push | window | |
Tracked | window | |
Tracked.pop | window | one call of remove |
Tracked.push | window | one call of add |
Tracked.state | window | O(1) |
Trie | strings | |
Trie.add | strings | |
Trie.clear | strings | O(1) |
Trie.contains | strings | O(|word|) |
Trie.count | strings | |
Trie.count_less | strings | O(|word| * |A|) |
Trie.count_prefix | strings | |
Trie.ends_at | strings | |
Trie.find | strings | |
Trie.is_empty | strings | O(1) |
Trie.kth | strings | O(depth * |A|) |
Trie.len | strings | O(1) |
Trie.new | strings | O(|A|) |
Trie.pass_at | strings | |
Trie.remove | strings | |
Trie.root | strings | O(1) |
Trie.step | strings | |
TwoSat | graph | |
TwoSat.add_eq | graph | O(1) amortized |
TwoSat.add_or | graph | O(1) amortized |
TwoSat.add_xor | graph | O(1) amortized |
TwoSat.at_most_one | graph | O(k) amortized |
TwoSat.clause | graph | |
TwoSat.implies | graph | O(1) amortized |
TwoSat.must | graph | O(1) amortized |
TwoSat.new | graph | O(|X|) |
TwoSat.solve | graph | O(|X| + clauses) |
Undo | window | |
Undo.mark | window | |
Undo.undo_to | window | |
Undoing | window | |
Undoing.pop | window | O(log n) applications of add amortized |
Undoing.push | window | O(1) applications of add amortized |
Undoing.push_entry | window | |
Undoing.state | window | O(1) |
Vec | geometry | |
Vec.add | geometry | |
Vec.angle | geometry | O(1) |
Vec.cross | geometry | O(1) |
Vec.dist | geometry | O(1) |
Vec.dist2 | geometry | O(1) |
Vec.div | geometry | |
Vec.dot | geometry | O(1) |
Vec.from_angle | geometry | O(1) |
Vec.len | geometry | O(1) |
Vec.mul | geometry | |
Vec.neg | geometry | |
Vec.norm2 | geometry | O(1) |
Vec.perp | geometry | O(1) |
Vec.perp_cw | geometry | O(1) |
Vec.rot | geometry | O(1) |
Vec.sub | geometry | |
Vec.unit | geometry | O(1) |
Vec3 | geometry | |
Vec3.add | geometry | |
Vec3.cross | geometry | O(1) |
Vec3.dist | geometry | O(1) |
Vec3.dist2 | geometry | O(1) |
Vec3.div | geometry | |
Vec3.dot | geometry | O(1) |
Vec3.len | geometry | O(1) |
Vec3.mul | geometry | |
Vec3.neg | geometry | |
Vec3.norm2 | geometry | O(1) |
Vec3.rot | geometry | O(1) |
Vec3.sub | geometry | |
Vec3.unit | geometry | O(1) |
Version | persistent | |
VirtualTree | tree | |
Visit | graph | |
Walk | graph | |
Walk.vertices | graph | O(1) to make, O(1) per vertex |
WaveletMatrix | segtree | |
WaveletMatrix.below | segtree | |
WaveletMatrix.count_in | segtree | O(log V) |
WaveletMatrix.count_lt | segtree | O(log V) |
WaveletMatrix.kth | segtree | O(log V) |
WaveletMatrix.new | segtree | O(|D| log V) time and memory |
WaveletMatrix.next_val | segtree | O(log V) |
WaveletMatrix.ones | segtree | |
WaveletMatrix.prev_val | segtree | O(log V) |
WaveletMatrix.quantile_sum | segtree | O(log V) |
WaveletMatrix.rank | segtree | O(log V) |
Weighted | graph | |
Weighted.w | graph | O(1) plus the cost of f under weighted |
WeightedNext | graph | |
Window | window | |
Window.all | window | O(1) |
Window.drop_front | window | |
Window.len | window | O(1) |
Window.new | window | O(1) |
Window.pop | window | O(1) amortized calls of op |
Window.push | window | O(1) amortized calls of op |
Window.push_back | window | |
Window<T, M>.pop | window | |
Window<T, M>.push | window | |
Wire | io | |
Wire.ask | io | O(|query|) plus the read of one T |
Wire.new | io | O(1) |
Word.rev | algebra | |
Word.rev | tree | |
XorBasis | matrix | |
XorBasis.add | matrix | O(W) |
XorBasis.basis_vecs | matrix | O(W) time and space |
XorBasis.contains | matrix | O(W) |
XorBasis.intersect | matrix | O(W^2) |
XorBasis.kth | matrix | O(W^2) |
XorBasis.max_xor | matrix | O(W) |
XorBasis.merge | matrix | O(W * o.rank) |
XorBasis.min_xor | matrix | O(W) |
XorBasis.monoid | matrix | O(W) (for the identity) |
XorBasis.new | matrix | O(W) |
XorBasis.rank | matrix | O(1) |
XorBasis.reduce | matrix | O(W) |
XorTrie | bitset | |
XorTrie.add | bitset | O(bits) time, up to bits new nodes |
XorTrie.child | bitset | |
XorTrie.clear | bitset | O(1) |
XorTrie.contains | bitset | O(bits) |
XorTrie.count | bitset | O(bits) |
XorTrie.count_xor_less | bitset | O(bits) |
XorTrie.extreme_xor | bitset | |
XorTrie.is_empty | bitset | O(1) |
XorTrie.kth_xor | bitset | O(bits) |
XorTrie.leaf | bitset | |
XorTrie.len | bitset | O(1) |
XorTrie.max_xor | bitset | O(bits) |
XorTrie.mex_xor | bitset | O(bits) |
XorTrie.min_xor | bitset | O(bits) |
XorTrie.new | bitset | O(1) |
XorTrie.remove | bitset | O(bits) |
XorTrie.reserve | bitset | O(nodes) time and space |
XorTrie.walk | bitset | |
XorTrie.xor_all | bitset | O(1) |