Skip to Content
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

A to Z

ItemModuleCost
Actionalgebra
Action.newalgebraO(1)
Action.ofalgebraO(1)
AddActionalgebra
Affinealgebra
Affine.evalalgebraO(1)
Affine.idalgebraO(1)
Affine.monoidalgebraO(1)
Affine.thenalgebraO(1)
AffineActionalgebra
AhoCorasickstrings
AhoCorasick.countsstrings
AhoCorasick.exit_linkstringsO(1)
AhoCorasick.fail_orderstringsO(states)
AhoCorasick.find_allstrings
AhoCorasick.hitstrings
AhoCorasick.lenstringsO(1)
AhoCorasick.linkstrings
AhoCorasick.newstrings
AhoCorasick.pattern_statestringsO(1)
AhoCorasick.rootstringsO(1)
AhoCorasick.stepstrings
AhoCorasick.words_atstrings
Anchorseq
Arcflow
Arc.revflowO(1)
Arenamarks
Arena.allocmarksO(1) amortized
Arena.clearmarksO(1)
Arena.getmarksO(1)
Arena.is_emptymarksO(1)
Arena.lenmarksO(1)
Arena.newmarksO(cap)
Arena.reservemarksO(cap)
Arena.setmarksO(1)
ArithDiffprefix
ArithDiff.addprefixO(1)
ArithDiff.add_arithprefixO(1)
ArithDiff.finishprefixO(|D|) time and space
ArithDiff.newprefixO(|D|) time and space
AssignActionalgebra
AugSortedBagbag
AugSortedBag.addbagO(log n) expected
AugSortedBag.allbagO(1)
AugSortedBag.countbagO(log n) expected
AugSortedBag.drop_minbag
AugSortedBag.eachbagO(1) amortized per step
AugSortedBag.extremebag
AugSortedBag.firstbagO(1)
AugSortedBag.fold_betweenbagO(log n) expected
AugSortedBag.fold_frombag
AugSortedBag.fold_gebagO(log n) expected
AugSortedBag.fold_gtbagO(log n) expected
AugSortedBag.fold_lebagO(log n) expected
AugSortedBag.fold_ltbagO(log n) expected
AugSortedBag.fold_uptobag
AugSortedBag.is_emptybagO(1)
AugSortedBag.lastbagO(1)
AugSortedBag.lenbagO(1)
AugSortedBag.mergebag
AugSortedBag.newbagO(1)
AugSortedBag.nthbagO(log n) expected
AugSortedBag.pullbag
AugSortedBag.rankbagO(log n) expected
AugSortedBag.rank_lebag
AugSortedBag.removebagO(log n) expected
AugSortedBag.reservebagO(cap) when the pool grows, O(1) otherwise
AugSortedBag.sizebag
AugSortedBag.splitbag
AugSortedBag.subbag
AugSortedSetbag
AugSortedSet.addbagO(log n) expected
AugSortedSet.allbagO(1)
AugSortedSet.containsbagO(log n) expected
AugSortedSet.eachbagO(1) amortized per step
AugSortedSet.firstbagO(1)
AugSortedSet.fold_betweenbagO(log n) expected
AugSortedSet.fold_gebagO(log n) expected
AugSortedSet.fold_gtbagO(log n) expected
AugSortedSet.fold_lebagO(log n) expected
AugSortedSet.fold_ltbagO(log n) expected
AugSortedSet.is_emptybagO(1)
AugSortedSet.lastbagO(1)
AugSortedSet.lenbagO(1)
AugSortedSet.newbagO(1)
AugSortedSet.nthbagO(log n) expected
AugSortedSet.rankbagO(log n) expected
AugSortedSet.removebagO(log n) expected
AugSortedSet.reservebagO(cap) when the pool grows, O(1) otherwise
BagCursorbag
Barrettmod
Barrett.mulmodO(1)
Barrett.newmodO(1)
Barrett.reducemodO(1)
BeatsSegTreebeats
BeatsSegTree.addbeatsO(log |D|)
BeatsSegTree.add_recbeats
BeatsSegTree.all_maxbeatsO(1)
BeatsSegTree.all_minbeatsO(1)
BeatsSegTree.all_sumbeatsO(1)
BeatsSegTree.apply_addbeats
BeatsSegTree.apply_chmaxbeats
BeatsSegTree.apply_chminbeats
BeatsSegTree.assignbeatsO(log |D|) amortized
BeatsSegTree.buildbeats
BeatsSegTree.chdivbeatsO(log |D| log V) amortized
BeatsSegTree.chmaxbeatsO(log |D|) amortized; O(log^2 |D|) amortized when mixed with add
BeatsSegTree.chmax_recbeats
BeatsSegTree.chminbeatsO(log |D|) amortized; O(log^2 |D|) amortized when mixed with add
BeatsSegTree.chmin_recbeats
BeatsSegTree.chmodbeatsO(log |D| log V) amortized
BeatsSegTree.div_recbeats
BeatsSegTree.getbeatsO(log |D|)
BeatsSegTree.max_recbeats
BeatsSegTree.max_valbeatsO(log |D|)
BeatsSegTree.min_recbeats
BeatsSegTree.min_valbeatsO(log |D|)
BeatsSegTree.newbeatsO(|D|)
BeatsSegTree.pullbeats
BeatsSegTree.pushbeats
BeatsSegTree.setbeatsO(log |D|)
BeatsSegTree.sumbeatsO(log |D|)
BeatsSegTree.sum_recbeats
BigIntmath
BigInt.absmathO(n)
BigInt.addmath
BigInt.divmath
BigInt.divmodmathO(n * m)
BigInt.from_intmathO(1)
BigInt.from_strmathO(s.len)
BigInt.gcdmathO(n^2)
BigInt.ltmath
BigInt.mulmath
BigInt.negmath
BigInt.showmath
BigInt.submath
BigInt.to_strmathO(n)
BitMatmatrix
BitMat.detmatrixO(n^3 / 64)
BitMat.getmatrixO(1)
BitMat.identitymatrixO(n^2 / 64) time and space
BitMat.inversematrixO(n^3 / 64)
BitMat.mulmatrixO(rows * cols * o.cols / 64)
BitMat.newmatrixO(rows * cols / 64) time and space
BitMat.rankmatrixO(rows * cols * min(rows, cols) / 64)
BitMat.setmatrixO(1)
BitMat.solvematrixO(rows * cols * min(rows, cols) / 64)
BitMat.solve_spacematrixO(rows * cols * min(rows, cols) / 64)
Bitsetbitset
Bitset.addbitsetO(1)
Bitset.anybitsetO(K / 64 + visited) words scanned and calls of pred
Bitset.bitandbitsetO(K / 64) time and space
Bitset.bitorbitsetO(K / 64) time and space
Bitset.bitxorbitsetO(K / 64) time and space
Bitset.clearbitsetO(K / 64)
Bitset.complementbitsetO(K / 64) time and space
Bitset.containsbitsetO(1)
Bitset.countbitsetO(1)
Bitset.count_belowbitsetO(K / 64)
Bitset.count_rangebitsetO(r.len / 64 + 1)
Bitset.eachbitsetO(K / 64 + len) to walk, O(1) per member amortized
Bitset.each_revbitsetO(K / 64 + len) to walk
Bitset.emptybitsetO(K / 64) time and space
Bitset.findbitsetO(K / 64 + visited)
Bitset.firstbitsetO(K / 64)
Bitset.flip_rangebitsetO(r.len / 64 + 1)
Bitset.frombitsetO(K) time, O(K / 64) space
Bitset.fullbitsetO(K / 64) time and space
Bitset.intersectbitsetO(K / 64)
Bitset.is_emptybitsetO(1)
Bitset.lenbitsetO(1)
Bitset.meetsbitsetO(K / 64), less on an early hit
Bitset.newbitsetO(K / 64) time and space
Bitset.nextbitsetO(K / 64)
Bitset.nthbitsetO(K / 64)
Bitset.ofbitsetO(K / 64 + xs.len) time, O(K / 64) space
Bitset.prevbitsetO(K / 64)
Bitset.recountbitset
Bitset.removebitsetO(1)
Bitset.rfindbitsetO(K / 64 + visited)
Bitset.setbitsetO(K / 64) time and space
Bitset.set_rangebitsetO(r.len / 64 + 1)
Bitset.shift_downbitsetO(K / 64)
Bitset.shift_orbitsetO(K / 64)
Bitset.shift_upbitsetO(K / 64)
Bitset.shiftedbitsetO(K / 64) time and space, for any k
Bitset.singlebitsetO(K / 64) time and space
Bitset.subset_sumsbitsetO(K sqrt(S) / 64) time, where S is the sum of weights; O(K / 64) space
Bitset.subtractbitsetO(K / 64)
Bitset.symmetricbitsetO(K / 64)
Bitset.togglebitsetO(1)
Bitset.trimbitset
Bitset.unionbitsetO(K / 64)
Bitset.withbitsetO(K / 64) time and space
Bitset.withoutbitsetO(K / 64) time and space
Bitset<D>.showbitset
Bitset<D>.subbitset
BucketCountbag
BucketCount.addbagO(1)
BucketCount.clearbagO(r.len)
BucketCount.countbagO(1)
BucketCount.count_ltbagO(sqrt(N))
BucketCount.is_emptybagO(1)
BucketCount.kthbagO(sqrt(N))
BucketCount.lenbagO(1)
BucketCount.newbagO(r.len)
BucketCount.removebagO(1)
ByAnglegeometry
ByAngle.ltgeometry
ByAngleFromgeometry
ByAngleFrom.ltgeometry
Centroidstree
Centroids.ancestorstreeO(1) per entry, O(log n) in all
Centroids.depthtreeO(1)
Centroids.newtreeO(n log n) time and memory
Centroids.parenttreeO(1)
Centroids.piecetreeO(size of the piece)
Circlegeometry
Circle.areageometryO(1)
Circle.circumferencegeometryO(1)
Circle.locategeometryO(1)
Circle.throughgeometryO(1)
ColorMatroidflow
ColorMatroid.newflowO(1); each rebuild is O(E)
Combmod
Comb.arrangemodO(1) amortized
Comb.catalanmodO(1) amortized
Comb.choosemodO(1) amortized for n < M.MOD; O(log_P n) otherwise
Comb.choose_lucasmod
Comb.derangemodO(1) amortized, O(n) table
Comb.ensuremod
Comb.factmodO(1) amortized
Comb.growmod
Comb.invmodO(1) amortized
Comb.inv_factmodO(1) amortized
Comb.multichoosemodO(1) amortized
Comb.multinomialmodO(ks.len) amortized
Comb.newmodO(min(limit, P))
Commutativealgebra
Complementgraph
Complement.outgraphO(|V| + deg u)
Compressedseq
Compressed.atseqO(log n)
Compressed.containsseqO(log n)
Compressed.first_geseqO(log n)
Compressed.first_gtseqO(log n)
Compressed.getseqO(1)
Compressed.last_leseqO(log n)
Compressed.last_ltseqO(log n)
Compressed.lenseqO(1)
Compressed.sliceseqO(r.len)
Compressed.try_atseqO(log n)
Concaveslope
Concave.add_absslopeO(log n) expected
Concave.add_constslopeO(1)
Concave.add_leftslopeO(log n) expected
Concave.add_linearslopeO(1)
Concave.add_quadraticslopeO(1)
Concave.add_rightslopeO(log n) expected
Concave.argmaxslopeO(log n) expected (O(n) in the current implementation)
Concave.atslopeO(log n) expected (O(c - lo + log n) in the current implementation)
Concave.count_at_leastslope
Concave.flatslopeO(|r| log |r|) expected
Concave.hislopeO(1)
Concave.loslopeO(1)
Concave.maxslopeO(log n) expected (O(n) in the current implementation)
Concave.max_convolveslopeO(|g| log n) expected, for |g| slopes in g
Concave.pointslopeO(1)
Concave.prefix_maxslopeO(log n) expected (O(n log n) in the current implementation)
Concave.reserveslopeO(n)
Concave.shiftslopeO(1)
Concave.slide_maxslopeO(b - a + log n) expected
Concave.suffix_maxslopeO(log n) expected (O(n log n) in the current implementation)
Convexslope
Convex.add_absslopeO(log n) expected
Convex.add_constslopeO(1)
Convex.add_leftslopeO(log n) expected
Convex.add_linearslopeO(1)
Convex.add_quadraticslopeO(1)
Convex.add_rightslopeO(log n) expected
Convex.argminslopeO(log n) expected (O(n) in the current implementation)
Convex.atslopeO(log n) expected (O(c - lo + log n) in the current implementation)
Convex.flatslopeO(|r| log |r|) expected
Convex.hislopeO(1)
Convex.loslopeO(1)
Convex.minslopeO(log n) expected (O(n) in the current implementation)
Convex.min_convolveslopeO(|g| log n) expected, for |g| slopes in g
Convex.pointslopeO(1)
Convex.prefix_minslopeO(log n) expected (O(n log n) in the current implementation)
Convex.shiftslopeO(1)
Convex.slide_minslopeO(b - a + log n) expected
Convex.suffix_minslopeO(log n) expected (O(n log n) in the current implementation)
CostFlowflow
CostFlow.addflowO(1) amortized; two arcs of memory
CostFlow.arcsflowO(E) for the whole walk
CostFlow.cancel_cyclesflowO(V E log V) worst case, by cost scaling
CostFlow.capflowO(1)
CostFlow.costflowO(1)
CostFlow.flowflowO(1)
CostFlow.min_cost_flowflowO(F E log V) for F augmenting paths, plus O(V E) once when a residual arc has a negative cost
CostFlow.newflowO(n) for n = V.count
CostFlow.potentialsflow
CostFlow.set_capflowO(1)
CostFlow.slopeflowas min_cost_flow
CostFlow.sourceflowO(1)
CostFlow.targetflowO(1)
Counterhashmap
Counter.absorbhashmapO(min(|self|, |other|)) expected
Counter.addhashmapO(1) expected amortized
Counter.clearhashmapO(n)
Counter.containshashmapO(1) expected
Counter.gethashmapO(1) expected
Counter.is_emptyhashmapO(1)
Counter.itemshashmapO(1) to make, O(1) per step
Counter.keyshashmapO(1) to make, O(1) per step
Counter.lenhashmapO(1)
Counter.most_commonhashmapO(n log n)
Counter.newhashmapO(1)
Counter.ofhashmapO(n) expected
Counter.removehashmapO(1) expected
Counter.reservehashmapO(cap) when the table grows, O(1) otherwise
Counter.sethashmapO(1) expected amortized
Counter.takehashmapO(1)
Counter.totalhashmapO(n)
Counter.valueshashmapO(1) to make, O(1) per step
Counter<K, Int>.popwindow
Counter<K, Int>.pushwindow
Curvedntt
Dequedeque
Deque.cleardequeO(1)
Deque.eachdequeO(1) per step
Deque.each_revdequeO(1) per step
Deque.firstdequeO(1)
Deque.getdequeO(1)
Deque.grow_todeque
Deque.is_emptydequeO(1)
Deque.itemsdequeO(1) to make, O(1) per step
Deque.lastdequeO(1)
Deque.lendequeO(1)
Deque.newdequeO(1); nothing is allocated until the first push
Deque.ofdequeO(n)
Deque.popdequeO(1)
Deque.pop_frontdequeO(1)
Deque.pop_front_whiledequeO(k) for k removed
Deque.pop_whiledequeO(k) for k removed
Deque.pushdequeO(1) amortized; a full ring doubles
Deque.push_frontdequeO(1) amortized; a full ring doubles
Deque.reservedequeO(1) when empty, O(cap) otherwise
Deque.rotate_leftdequeO(min(k, n - k)) after reducing k mod n
Deque.rotate_rightdequeO(min(k, n - k)) after reducing k mod n
Deque.setdequeO(1)
Deque.takedequeO(1)
Deque.to_listdequeO(n), one new List
Descalgebra
Desc<T>.ltalgebra
Desc<T>.showalgebra
Diffprefix
Diff.addprefixO(1)
Diff.finishprefixO(|D|) time and space
Diff.newprefixO(|D|) time and space
Dir4grid
Dir4.allgridO(1)
Dir4.backgridO(1)
Dir4.ccwgridO(1)
Dir4.cwgridO(1)
Dir4.deltagridO(1)
Dir4.downgridO(1)
Dir4.fromgridO(1)
Dir4.leftgridO(1)
Dir4.rightgridO(1)
Dir4.upgridO(1)
Dir8grid
Dir8.allgridO(1)
Dir8.backgridO(1)
Dir8.ccwgridO(1)
Dir8.cwgridO(1)
Dir8.deltagridO(1)
Dir8.fromgridO(1)
DirichletSummath
DirichletSum.newmathO(f_small.len) to build; queries as sum
DirichletSum.summathO(1) cached; O(n^(2/3)) total across all n / i queries
Disjointntt
DisjointSparseTablesparse
DisjointSparseTable.allsparseO(1)
DisjointSparseTable.foldsparseO(1), at most one op call
DisjointSparseTable.getsparseO(1)
DisjointSparseTable.newsparseO(|D| log |D|) time and memory, op called O(|D| log |D|) times
DisjointSparseTable.try_foldsparseO(1)
Dsudsu
Dsu.componentsdsuO(1)
Dsu.finddsuO(alpha(n)) amortized; O(log n) after the first mark
Dsu.find_orddsu
Dsu.groupsdsuO(n alpha(n)); allocates the lists
Dsu.markdsuO(1)
Dsu.mergedsuas unite
Dsu.newdsuO(n) for n = V.count; one [V] array
Dsu.rootsdsuO(n) for the whole walk, no allocation
Dsu.samedsuO(alpha(n)) amortized; O(log n) after the first mark
Dsu.sizedsuO(alpha(n)) amortized; O(log n) after the first mark
Dsu.undo_todsuO(1) per undone unite
Dsu.unitedsuO(alpha(n)) amortized; O(log n) after the first mark, plus one log entry
Dsu<V>.markwindow
Dsu<V>.undo_towindow
DsuOfdsu
DsuOf.componentsdsuO(1)
DsuOf.finddsuO(alpha(n)) amortized; O(log n) after the first mark
DsuOf.getdsuO(alpha(n)) amortized; O(log n) after the first mark
DsuOf.groupsdsuO(n alpha(n)); allocates the lists
DsuOf.markdsuO(1)
DsuOf.mergedsuas unite
DsuOf.newdsuO(n) calls of init; three [V] arrays
DsuOf.rootsdsuO(n) for the whole walk, no allocation
DsuOf.samedsuO(alpha(n)) amortized; O(log n) after the first mark
DsuOf.setdsuO(alpha(n)) amortized; O(log n) after the first mark, plus one log entry
DsuOf.sizedsuO(alpha(n)) amortized; O(log n) after the first mark
DsuOf.undo_todsuO(1) per undone change
DsuOf.unitedsuas Dsu.unite, plus one call of join
DsuOf.valuesdsuO(n) for the whole walk, no allocation
DsuOf<V, T>.markwindow
DsuOf<V, T>.undo_towindow
DualFenwickfenwick
DualFenwick.addfenwickO(log |D|)
DualFenwick.add_atfenwick
DualFenwick.clearfenwickO(|D|)
DualFenwick.getfenwickO(log |D|)
DualFenwick.newfenwickO(|D|) time; memory |D| + 1 values
DynamicAhoCorasickstrings
DynamicAhoCorasick.addstringsO(|pattern| * |A| * log n) amortized
DynamicAhoCorasick.count_matchesstringsO(|text| * log n)
DynamicAhoCorasick.is_emptystringsO(1)
DynamicAhoCorasick.lenstringsO(1)
DynamicAhoCorasick.newstringsO(1)
DynamicAhoCorasick.removestringsO(|pattern| * |A| * log n) amortized
DynamicHashstrings
DynamicHash.allstringsO(1)
DynamicHash.getstringsO(log n)
DynamicHash.is_emptystringsO(1)
DynamicHash.is_palindromestringsO(log n)
DynamicHash.lenstringsO(1)
DynamicHash.newstringsO(n)
DynamicHash.rev_getstringsO(log n)
DynamicHash.setstringsO(log n)
DynamicOrderTreesegtree
DynamicOrderTree.belowsegtree
DynamicOrderTree.bumpsegtree
DynamicOrderTree.count_insegtreeO(log^2 |D|)
DynamicOrderTree.count_ltsegtreeO(log^2 |D|)
DynamicOrderTree.getsegtreeO(1)
DynamicOrderTree.kthsegtreeO(log^2 |D|)
DynamicOrderTree.newsegtreeO(|D| log^2 |D|) time and memory
DynamicOrderTree.setsegtreeO(log^2 |D|)
DynamicOrderTree.span_countsegtree
DynBitsetbitset
DynBitset.addbitsetO(1)
DynBitset.capbitsetO(1)
DynBitset.clearbitsetO(cap / 64)
DynBitset.containsbitsetO(1)
DynBitset.count_belowbitsetO(cap / 64)
DynBitset.count_rangebitsetO(r.len / 64 + 1)
DynBitset.eachbitsetO(cap / 64 + len) to walk
DynBitset.each_revbitsetO(cap / 64 + len) to walk
DynBitset.firstbitsetO(cap / 64)
DynBitset.fullbitsetO(cap / 64) time and space
DynBitset.intersectbitsetO(cap / 64)
DynBitset.is_emptybitsetO(1)
DynBitset.lastbitsetO(cap / 64)
DynBitset.lenbitsetO(1)
DynBitset.meetsbitsetO(cap / 64), less on an early hit
DynBitset.newbitsetO(cap / 64) time and space
DynBitset.nextbitsetO(cap / 64)
DynBitset.nthbitsetO(cap / 64)
DynBitset.prevbitsetO(cap / 64)
DynBitset.recountbitset
DynBitset.removebitsetO(1)
DynBitset.resizebitsetO(new_cap / 64) time and space
DynBitset.setbitsetO(1)
DynBitset.shift_downbitsetO(cap / 64)
DynBitset.shift_orbitsetO(cap / 64)
DynBitset.shift_upbitsetO(cap / 64)
DynBitset.subset_sumsbitsetO(cap sqrt(S) / 64) time, where S is the sum of weights; O(cap / 64) space
DynBitset.subtractbitsetO(cap / 64)
DynBitset.symmetricbitsetO(cap / 64)
DynBitset.togglebitsetO(1)
DynBitset.trimbitset
DynBitset.unionbitsetO(cap / 64)
Edgegraph
Edgedgraph
Edged.egraphO(1)
EdgedNextgraph
ErasableHeapheap
ErasableHeap.clearheapO(1)
ErasableHeap.is_emptyheapO(1)
ErasableHeap.lenheapO(1)
ErasableHeap.newheapO(1)
ErasableHeap.peekheapO(log n) amortized
ErasableHeap.popheapO(log n) amortized
ErasableHeap.pruneheap
ErasableHeap.pushheapO(log n)
ErasableHeap.removeheapO(log n)
ErasableHeap.takeheapO(1)
EulerTourTreetree
EulerTourTree.connectedtreeexpected O(log n)
EulerTourTree.cuttreeexpected O(log n)
EulerTourTree.fold_subtreeexpected O(log n)
EulerTourTree.fold_treetreeexpected O(log n)
EulerTourTree.gettreeO(1)
EulerTourTree.lentreeexpected O(log n)
EulerTourTree.linktreeexpected O(log n)
EulerTourTree.newtreeO(n)
EulerTourTree.settreeexpected O(log n)
Eventstree
Events.entertreeO(1)
Events.exittreeO(1)
Events.pathtreeO(log n)
Events.subtreeO(1)
Fenwickfenwick
Fenwick.addfenwickO(log |D|)
Fenwick.allfenwickO(1)
Fenwick.clearfenwickO(|D|)
Fenwick.first_gefenwickO(log |D|)
Fenwick.first_gtfenwickO(log |D|)
Fenwick.foldfenwickO(log |D|)
Fenwick.getfenwickO(log |D|)
Fenwick.kthfenwickO(log |D|)
Fenwick.newfenwickO(|D|) time; memory |D| + 1 values
Fenwick.prefixfenwickO(log |D|)
Fenwick.setfenwickO(log |D|)
Fenwick.suffixfenwickO(log |D|)
Fenwick2Dfenwick
Fenwick2D.addfenwickO(log |R| log |C|)
Fenwick2D.clearfenwickO(|R| |C|)
Fenwick2D.cornerfenwick
Fenwick2D.foldfenwickO(log |R| log |C|)
Fenwick2D.getfenwickO(log |R| log |C|)
Fenwick2D.newfenwickO(|R| |C|) time; memory (|R| + 1)(|C| + 1) values
Fenwick2D.prefixfenwickO(log |R| log |C|)
FillOrderprefix
FillPrefixprefix
FillPrefix.foldprefixO(1)
FillPrefix.prefixprefixO(1)
FillPrefix.setprefixO(1)
Filteredseq
Filtered.srcseqO(1)
FlatMaphashmap
FlatMap.absorbhashmapO(min(|self|, |other|)) expected
FlatMap.clearhashmapO(capacity)
FlatMap.containshashmapO(1) expected
FlatMap.gethashmapO(1) expected
FlatMap.get_or_inserthashmapO(1) expected amortized
FlatMap.is_emptyhashmapO(1)
FlatMap.itemshashmapO(1) to make, O(capacity) to walk
FlatMap.keyshashmapO(1) to make, O(capacity) to walk
FlatMap.lenhashmapO(1)
FlatMap.newhashmapO(cap)
FlatMap.rehashhashmap
FlatMap.removehashmapO(1) expected
FlatMap.reservehashmapO(cap) when the table grows, O(1) otherwise
FlatMap.sethashmapO(1) expected amortized
FlatMap.slothashmap
FlatMap.takehashmapO(1)
FlatMap.valueshashmapO(1) to make, O(capacity) to walk
Fliplazy
Flip.oflazyO(1)
Flip.oplazyO(1)
FlipActionalgebra
FlowGraphflow
FlowGraph.addflowO(1) amortized; two arcs of memory
FlowGraph.add_bothflowO(1) amortized; two arcs of memory
FlowGraph.arcsflowO(E) for the whole walk
FlowGraph.augmentflow
FlowGraph.capflowO(1)
FlowGraph.closeflow
FlowGraph.cut_arcsflowO(V + E)
FlowGraph.flowflowO(1)
FlowGraph.levelsflow
FlowGraph.max_flowflowO(V² E); O(E sqrt V) when every capacity is 1
FlowGraph.min_cutflowO(V + E)
FlowGraph.newflowO(n) for n = V.count
FlowGraph.outflowO(deg u) for the whole walk
FlowGraph.pathsflowO(P (V + E)) for P paths
FlowGraph.pushflow
FlowGraph.push_relabelflowO(V² sqrt E)
FlowGraph.resetflowO(E)
FlowGraph.residualflowO(1)
FlowGraph.set_capflowO(1)
FlowGraph.sourceflowO(1)
FlowGraph.targetflowO(1)
Functionalgraph
Functional<V>.aftergraphO(log k)
Functional<V>.cycle_lengraphO(1)
Functional<V>.cyclesgraphO(n)
Functional<V>.depthgraphO(1)
Functional<V>.distgraphO(log n)
Functional<V>.jump_whilegraphO(log n)
Functional<V>.liftgraph
Functional<V>.newgraphO(n log n)
Functional<V>.on_cyclegraphO(1)
Functional<V>.root_ofgraphO(1)
Graphgraph
Graph.atgraphO(1)
Graph.deggraphO(1)
Graph.dfs_treegraphO(n + m)
Graph.directedgraphO(n + m) time and memory, plus m calls of keep
Graph.edgesgraphO(1) to make, O(1) per edge
Graph.hasgraphO(deg u)
Graph.hopsgraphO(n (n + m)) time, O(n^2) memory
Graph.listsgraphO(n + m)
Graph.matrixgraphO(n^2 + m) time, O(n^2) memory
Graph.nextgraphO(1) per vertex yielded
Graph.ofgraphO(n + m)
Graph.onlygraphO(1) to make; keep and from run per arc walked
Graph.outgraphO(1) to make, O(1) per arc
Graph.peelgraphO(n + m) plus the calls of ready and on_remove
Graph.spanning_treegraphO(n + m)
Graph.transposegraphO(n + m)
Graph.undirectedgraphO(n + m) time and memory, plus 2m calls of keep
Graph.weightedgraphO(1) to make; f runs on every arc read
GraphicMatroidflow
GraphicMatroid.newflowO(1); each rebuild is O(E alpha(V))
Groupalgebra
Group.ofalgebraO(1)
HalfPlanegeometry
HalfPlane.from_linegeometryO(1)
HalfPlane.sidegeometryO(1)
HalfPlane.throughgeometryO(1)
Hash2Dstrings
Hash2D.newstrings
Hash2D.rectstrings
Hash61strings
Hashablestrings
Hashable.hash_tokenstrings
HashValstrings
HashVal.hash_tokenstringsO(1)
HasIdalgebra
HasId.idalgebra
HasInvalgebra
HasInv.invalgebra
Heapheap
Heap.clearheapO(1)
Heap.drainheapO(log n) per step
Heap.is_emptyheapO(1)
Heap.lenheapO(1)
Heap.lessheap
Heap.newheapO(1)
Heap.ofheapO(n)
Heap.peekheapO(1)
Heap.popheapO(log n)
Heap.pushheapO(log n), amortized over list growth
Heap.push_allheapO(k log n) for k items
Heap.push_popheapO(log n); O(1) when x is returned
Heap.replace_topheapO(log n)
Heap.reserveheapO(cap) when the storage grows, O(1) otherwise
Heap.sift_downheap
Heap.takeheapO(1)
HistoricBeatsSegTreebeats
HistoricBeatsSegTree.addbeatsO(log |D|)
HistoricBeatsSegTree.applybeats
HistoricBeatsSegTree.askbeats
HistoricBeatsSegTree.buildbeats
HistoricBeatsSegTree.chmaxbeatsO(log |D|) amortized; O(log^2 |D|) amortized when mixed with add
HistoricBeatsSegTree.chminbeatsO(log |D|) amortized; O(log^2 |D|) amortized when mixed with add
HistoricBeatsSegTree.composebeats
HistoricBeatsSegTree.givebeats
HistoricBeatsSegTree.hist_maxbeatsO(log |D|)
HistoricBeatsSegTree.hist_sumbeatsO(log |D|)
HistoricBeatsSegTree.max_valbeatsO(log |D|)
HistoricBeatsSegTree.newbeatsO(|D|)
HistoricBeatsSegTree.pullbeats
HistoricBeatsSegTree.pushbeats
HistoricBeatsSegTree.querybeats
HistoricBeatsSegTree.sumbeatsO(log |D|)
HistoricBeatsSegTree.updbeats
HistoricBeatsSegTree.updatebeats
Idmarks
Idempotentalgebra
IncrementalBridgesgraph
IncrementalBridges<V>.addgraphO(log n) amortized
IncrementalBridges<V>.newgraphO(n)
IncrementalBridges<V>.samegraphO(alpha)
IncrementalBridges<V>.two_edge_samegraphO(alpha)
IndexedHeapheap
IndexedHeap.beforeheap
IndexedHeap.clearheapO(len)
IndexedHeap.containsheapO(1)
IndexedHeap.decreaseheapO(log n)
IndexedHeap.getheapO(1)
IndexedHeap.increaseheapO(log n)
IndexedHeap.is_emptyheapO(1)
IndexedHeap.lenheapO(1)
IndexedHeap.newheapO(|D|)
IndexedHeap.peekheapO(1)
IndexedHeap.popheapO(log n)
IndexedHeap.removeheapO(log n)
IndexedHeap.setheapO(log n)
IndexedHeap.sift_downheap
IndexedHeap.sift_upheap
IndexedHeap.swap_atheap
Internermarks
Interner.clearmarksO(1)
Interner.containsmarksO(1) expected
Interner.getmarksO(1) expected
Interner.idmarksO(1) expected
Interner.is_emptymarksO(1)
Interner.keymarksO(1)
Interner.lenmarksO(1)
Interner.newmarksO(1)
Interner.reservemarksO(cap)
IntervalMapinterval
IntervalMap.assignintervalO((1 + overwritten) log runs) amortized
IntervalMap.assign_pointintervalO(log runs)
IntervalMap.eachintervalO(1) per run
IntervalMap.each_revintervalO(1) per run
IntervalMap.first_whereintervalO(log runs + skipped) for skipped runs that fail ok
IntervalMap.fromintervalO(|D|)
IntervalMap.getintervalO(log runs)
IntervalMap.newintervalO(1)
IntervalMap.rangeintervalO(log runs + k) for k pieces
IntervalMap.run_atintervalO(log runs)
IntervalMap.runsintervalO(1)
IntervalMap.setintervalO(log runs)
IntervalSetinterval
IntervalSet.addintervalO((1 + merged) log runs) amortized
IntervalSet.containsintervalO(log runs)
IntervalSet.contains_rangeintervalO(log runs)
IntervalSet.coveredintervalO(1)
IntervalSet.eachintervalO(1) per run
IntervalSet.newintervalO(1)
IntervalSet.next_coveredintervalO(log runs)
IntervalSet.next_gapintervalO(log runs)
IntervalSet.removeintervalO((1 + split) log runs) amortized
IntervalSet.run_atintervalO(log runs)
IntervalSet.runsintervalO(1)
ioio
Itemsseq
Items.srcseqO(1)
JumpTreetree
JumpTree.addtreeO(1)
JumpTree.ancestortreeO(log n)
JumpTree.depthtreeO(1)
JumpTree.disttreeO(log n)
JumpTree.jumptreeO(log n)
JumpTree.jump_whiletreeO(log n) calls of pred
JumpTree.lcatreeO(log n)
JumpTree.newtreeO(n)
JumpTree.parenttreeO(1)
JumpTree.root_oftreeO(log n)
Keysseq
KmpAutomatonstrings
KmpAutomaton.find_allstringsO(|text|)
KmpAutomaton.lenstringsO(1)
KmpAutomaton.linkstringsO(1)
KmpAutomaton.newstringsO(|pat| * |A|)
KmpAutomaton.stepstringsO(1)
KruskalTreetree
KruskalTree.bottlenecktreeO(log n)
KruskalTree.reachtreeO(log n)
KruskalTree.toptreeO(log n) calls of ok
KruskalTree.treetreeO(1); built with the tree
KruskalTree.uptreeO(n) calls of op and leaf
Layerstree
Layers.belowtreeO(log n)
Layers.leveltreeO(1)
Layers.postreeO(1)
LazyEulerTourTreetree
LazyEulerTourTree.apply_subtreeexpected O(log n)
LazyEulerTourTree.apply_treetreeexpected O(log n)
LazyEulerTourTree.connectedtreeexpected O(log n)
LazyEulerTourTree.cuttreeexpected O(log n)
LazyEulerTourTree.fold_subtreeexpected O(log n)
LazyEulerTourTree.fold_treetreeexpected O(log n)
LazyEulerTourTree.gettreeexpected O(log n)
LazyEulerTourTree.lentreeexpected O(log n)
LazyEulerTourTree.linktreeexpected O(log n)
LazyEulerTourTree.newtreeO(n)
LazyEulerTourTree.settreeexpected O(log n)
LazyLinkCuttree
LazyLinkCut.accesstree
LazyLinkCut.apply_pathtreeamortized O(log n)
LazyLinkCut.connectedtreeamortized O(log n)
LazyLinkCut.cuttreeamortized O(log n)
LazyLinkCut.disttreeamortized O(log n)
LazyLinkCut.fold_pathtreeamortized O(log n)
LazyLinkCut.gettreeamortized O(log n)
LazyLinkCut.jumptreeamortized O(log n)
LazyLinkCut.lcatreeamortized O(log n)
LazyLinkCut.linktreeamortized O(log n), with one root_of to check the trees differ
LazyLinkCut.make_roottreeamortized O(log n)
LazyLinkCut.newtreeO(n)
LazyLinkCut.pulltree
LazyLinkCut.pushtree
LazyLinkCut.puttree
LazyLinkCut.root_oftreeamortized O(log n)
LazyLinkCut.rotatetree
LazyLinkCut.settreeamortized O(log n)
LazyLinkCut.splaytree
LazyLinkCut.toptree
LazyLinkCut.turntree
LazyTreaplazy
LazyTreap.appendlazyO(log n) expected
LazyTreap.applylazyO(log n) expected
LazyTreap.apply_alllazyO(1)
LazyTreap.apply_rangelazyO(log n) expected
LazyTreap.copy_fromlazy
LazyTreap.downlazy
LazyTreap.erase_atlazyO(log n) expected
LazyTreap.erase_rangelazyO(log n) expected
LazyTreap.getlazyO(log n) expected
LazyTreap.inslazy
LazyTreap.insertlazyO(log n) expected
LazyTreap.insert_atlazyO(log n) expected
LazyTreap.is_emptylazyO(1)
LazyTreap.lenlazyO(1)
LazyTreap.mergelazy
LazyTreap.newlazyO(1)
LazyTreap.prioritylazy
LazyTreap.pulllazy
LazyTreap.pushlazyO(log n) expected
LazyTreap.putlazy
LazyTreap.reservelazyO(n) when it grows, else O(1)
LazyTreap.reverselazyO(log n) expected
LazyTreap.split_atlazyO(log n) expected
LazyTreap.split_poslazy
LazyTreap.split_vallazy
LazyTreap.sz_oflazy
LazyTreap.takelazyO(k + log n)
LazyTreap.to_listlazyO(n)
LazyTreap.walklazy
LcaTabletree
LcaTable.disttreeO(1)
LcaTable.lcatreeO(1)
LcaTable.newtreeO(n log n) time and memory
LiChaodp
LiChao.adddpO(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.atdpO(log n) for n = over.len
LiChao.cleardpO(1) amortized
LiChao.kiddp
LiChao.line_atdpO(log n) for n = over.len
LiChao.newdpO(1)
LiChao.settledp
LiChao.winsdp
Lifttree
Lift.ancestortreeO(log n)
Lift.climbtreeO(log n) calls of ok
Lift.climb_whiletreeO(log n) calls of ok and op
Lift.depthtreeO(1)
Lift.foldtreeO(log n) calls of op
Lift.lcatreeO(log n)
Lift.newtreeO(n log n) time and memory
Lift.oftreeO(n log n) time and memory, n calls of next
Lift.parenttreeO(1)
Linedp
Line.atdpO(1)
LinearRmqsparse
LinearRmq.argbestsparseO(1)
LinearRmq.bestsparseO(1)
LinearRmq.bettersparse
LinearRmq.in_blocksparse
LinearRmq.newsparseO(|D|) time and memory
LinearRmq.try_bestsparseO(1)
LineContainerdp
LineContainer.adddpO(log n) amortized
LineContainer.atdpO(log n)
LineContainer.bestdp
LineContainer.drop_enddp
LineContainer.enddp
LineContainer.floor_divdp
LineContainer.lendpO(1)
LineContainer.line_atdpO(log n)
LineContainer.meetdp
LineContainer.mergedp
LineContainer.signdp
LineContainer.splitdp
LinkCuttree
LinkCut.accesstree
LinkCut.connectedtreeamortized O(log n)
LinkCut.cuttreeamortized O(log n)
LinkCut.disttreeamortized O(log n)
LinkCut.fold_pathtreeamortized O(log n)
LinkCut.gettreeO(1)
LinkCut.jumptreeamortized O(log n)
LinkCut.lcatreeamortized O(log n)
LinkCut.linktreeamortized O(log n), with one root_of to check the trees differ
LinkCut.make_roottreeamortized O(log n)
LinkCut.newtreeO(n)
LinkCut.pulltree
LinkCut.pushtree
LinkCut.root_oftreeamortized O(log n)
LinkCut.rotatetree
LinkCut.settreeamortized O(log n)
LinkCut.splaytree
LinkCut.toptree
LinkCut.turntree
LinkedListdeque
LinkedList.bwddeque
LinkedList.cleardequeO(1)
LinkedList.eachdequeO(1) per step
LinkedList.each_revdequeO(1) per step
LinkedList.firstdequeO(1)
LinkedList.from_listdequeO(n)
LinkedList.fwddeque
LinkedList.is_emptydequeO(1)
LinkedList.lastdequeO(1)
LinkedList.lendequeO(1)
LinkedList.newdequeO(1)
LinkedList.nodedeque
LinkedList.ofdequeO(1)
LinkedList.popdequeO(1)
LinkedList.pop_frontdequeO(1)
LinkedList.pushdequeO(1)
LinkedList.push_frontdequeO(1)
LinkedList.reversedequeO(1)
LinkedList.set_bwddeque
LinkedList.set_fwddeque
LinkedList.splice_backdequeO(1)
LinkedList.splice_frontdequeO(1)
Litgraph
Lit.flipgraphO(1)
Locationgeometry
LongPathstree
LongPaths.slottreeO(1)
LongPaths.slotstreeO(1)
Mappedseq
Mapped.srcseqO(1)
Markdsu
MarkMapmarks
MarkMap.clearmarksO(1) amortized; O(|D|) on the call that wraps the counter
MarkMap.containsmarksO(1)
MarkMap.getmarksO(1)
MarkMap.is_emptymarksO(1)
MarkMap.lenmarksO(1)
MarkMap.newmarksO(|D|)
MarkMap.removemarksO(1)
MarkMap.setmarksO(1)
Marksmarks
Marks.addmarksO(1)
Marks.clearmarksO(1) amortized; O(|D|) on the call that wraps the counter
Marks.containsmarksO(1)
Marks.is_emptymarksO(1)
Marks.lenmarksO(1)
Marks.newmarksO(|D|)
Marks.removemarksO(1)
Matmatrix
Mat.adjugatematrixO(n^3) time, O(n^2) space
Mat.atmatrixO(1)
Mat.char_polymatrixO(n^3) time, O(n^2) space
Mat.detmatrixO(n^3) time, O(n^2) space
Mat.det_modmatrixO(n^3 log m)
Mat.filledmatrixO(rows * cols) time and space
Mat.from_flatmatrixO(rows * cols) time and space
Mat.from_rowsmatrixO(rows * cols) time and space
Mat.getmatrixO(1)
Mat.identitymatrixO(n^2) time and space
Mat.inversematrixO(n^3) time, O(n^2) space
Mat.mul_vecmatrixO(rows * cols) time, O(rows) space
Mat.newmatrixO(rows * cols) time and space
Mat.pfaffianmatrixO(n^3) time, O(n^2) space
Mat.productmatrixO(n^2) time and space (for the identity)
Mat.rankmatrixO(rows * cols * min(rows, cols)) time, O(rows * cols) space
Mat.rrefmatrixO(rows * cols * min(rows, cols)) time, O(rows * cols) space
Mat.setmatrixO(1)
Mat.solvematrixO(rows * cols * min(rows, cols)) time, O(rows * cols) space
Mat.solve_spacematrixO(rows * cols * min(rows, cols)) time, O(rows * cols) space
Mat.transposematrixO(rows * cols) time and space
Mat.zerosmatrixO(rows * cols) time and space
Mat<T>.addmatrix
Mat<T>.mulmatrix
Mat<T>.powmatrix
Mat<T>.submatrix
Matchingflow
Matching.addflowO(1) amortized
Matching.augmentflowO(V + E)
Matching.augment_allflowO(E sqrt V)
Matching.backflowO(1)
Matching.coverflowO(V + E)
Matching.lenflowO(1)
Matching.mateflowO(1)
Matching.newflowO(L + R)
Matching.removeflowO(V + E)
MatPowmatrix
MatPow.apply_powmatrixO(n^2 log e) time, O(n) space
MatPow.newmatrixO(n^3 log max_exp) time, O(n^2 log max_exp) space
Matroidflow
Matroid.can_addflow
Matroid.can_swapflow
Matroid.rebuildflow
MaxCountalgebra
MaxCount.joinalgebraO(1)
MaxCount.monoidalgebraO(1)
MaxCount.ofalgebraO(1)
MaxHeapheap
MaxHeap.clearheapO(1)
MaxHeap.drainheapO(n log n)
MaxHeap.is_emptyheapO(1)
MaxHeap.lenheapO(1)
MaxHeap.newheapO(1)
MaxHeap.ofheapO(n)
MaxHeap.peekheapO(1)
MaxHeap.popheapO(log n)
MaxHeap.pushheapO(log n)
MaxHeap.push_allheapO(n + k log(n + k))
MaxHeap.push_popheapO(log n); O(1) when x is returned
MaxHeap.replace_topheapO(log n)
MaxHeap.reserveheapO(cap) when the storage grows, O(1) otherwise
MaxHeap.takeheapO(1)
MaxSubalgebra
MaxSub.addalgebra
MaxSub.emptyalgebraO(1)
MaxSub.joinalgebraO(1)
MaxSub.monoidalgebraO(1)
MaxSub.mulalgebra
MaxSub.ofalgebraO(1)
MaxSub.revalgebra
MaxSub.scalealgebraO(1)
MaxSub.try_bestalgebraO(1)
MeldHeapheap
MeldHeap.absorbheapO(log n)
MeldHeap.add_allheapO(1)
MeldHeap.clearheapO(1)
MeldHeap.drainheapO(n log n)
MeldHeap.is_emptyheapO(1)
MeldHeap.lenheapO(1)
MeldHeap.lessheap
MeldHeap.meldheapO(log n)
MeldHeap.mergeheap
MeldHeap.newheapO(1)
MeldHeap.nodeheap
MeldHeap.ofheapO(n)
MeldHeap.peekheapO(1)
MeldHeap.popheapO(log n)
MeldHeap.pushheapO(log n)
MeldHeap.push_allheapO(k log n) for k items
MeldHeap.push_downheap
MeldHeap.rank_ofheap
MeldHeap.takeheapO(1)
MeldHeap.topheapO(1)
MergeSegsegtree
MergeSeg.first_alivesegtreeO(log |D|) amortized
MergeSeg.mergesegtreeO(log |D|) amortized per node absorbed
MergeSeg.pop_minsegtree
MergeSeg.push_rawsegtree
MergeSeg.singletonsegtreeO(log |D|)
MergeSortTreesegtree
MergeSortTree.count_gesegtreeO(log^2 |D|)
MergeSortTree.count_gtsegtreeO(log^2 |D|)
MergeSortTree.count_insegtreeO(log^2 |D|)
MergeSortTree.count_lesegtreeO(log^2 |D|)
MergeSortTree.count_ltsegtreeO(log^2 |D|)
MergeSortTree.first_gesegtreeO(log^2 |D|)
MergeSortTree.last_lesegtreeO(log^2 |D|)
MergeSortTree.lower_idxsegtree
MergeSortTree.newsegtreeO(|D| log |D|) time and memory
MergeSortTree.upper_idxsegtree
MinCountalgebra
MinCount.joinalgebraO(1)
MinCount.monoidalgebraO(1)
MinCount.ofalgebraO(1)
MinMaxHeapheap
MinMaxHeap.bubble_upheap
MinMaxHeap.clearheapO(1)
MinMaxHeap.firstheapO(1)
MinMaxHeap.is_emptyheapO(1)
MinMaxHeap.lastheapO(1)
MinMaxHeap.lenheapO(1)
MinMaxHeap.lessheap
MinMaxHeap.max_atheap
MinMaxHeap.newheapO(1)
MinMaxHeap.ofheapO(n)
MinMaxHeap.pop_firstheapO(log n)
MinMaxHeap.pop_lastheapO(log n)
MinMaxHeap.pushheapO(log n), amortized over list growth
MinMaxHeap.remove_atheap
MinMaxHeap.reserveheapO(cap) when the storage grows, O(1) otherwise
MinMaxHeap.swapheap
MinMaxHeap.takeheapO(1)
MinMaxHeap.trickle_downheap
Modmod
Mod.from_intmodO(1)
Mod.invmodO(log P)
Mod.inv_allmodO(n + log P)
Mod.logmodO(sqrt P)
Mod.newmodO(1)
Mod.sqrtmodO(log^2 P)
Mod.try_invmodO(log P)
Mod<P>.addmod
Mod<P>.divmod
Mod<P>.mulmod
Mod<P>.negmod
Mod<P>.powmod
Mod<P>.readmod
Mod<P>.showmod
Mod<P>.submod
ModCombmod
ModComb.choosemodO(omega(m) log n)
ModComb.newmodO(sum p_i^e_i)
MongePathdp
MongePath.lendpO(1)
MongePath.nextdpO(1) amortized calls of cost
MongePath.setupdp
MongePath.valdpO(1)
MongePath.wdp
Monoidalgebra
Monoid.ofalgebraO(1)
MonoStackseq
MonoStack.clearseqO(1)
MonoStack.is_emptyseqO(1)
MonoStack.lenseqO(1)
MonoStack.markseqO(1)
MonoStack.popsseq
MonoStack.pushseqO(1) amortized
MonoStack.topseqO(1)
MonoStack.undo_toseqO(1) amortized per undone push
MonotoneHulldp
MonotoneHull.adddpO(1) amortized
MonotoneHull.atdpO(log n)
MonotoneHull.at_nextdpO(1) amortized
MonotoneHull.best_nextdpO(1) amortized
MonotoneHull.cleardpO(1)
MonotoneHull.covereddp
MonotoneHull.lendpO(1)
MonotoneHull.pop_linedp
MonotoneHull.signdp
MonotoneHull.val_atdp
Nextgraph
Next.outgraphO(1) per arc yielded
OnlineHullgeometry
OnlineHull.addgeometryO(log n) amortized
OnlineHull.area2geometryO(1)
OnlineHull.cleargeometryO(n)
OnlineHull.extremegeometryO(log n)
OnlineHull.is_emptygeometryO(1)
OnlineHull.itergeometryO(n)
OnlineHull.lengeometryO(1)
OnlineHull.locategeometryO(log n)
OnlineHull.newgeometryO(1)
OnlineHull.verticesgeometryO(n) time and memory
OnlineLisseq
OnlineLis.clearseqO(1)
OnlineLis.is_emptyseqO(1)
OnlineLis.lenseqO(1)
OnlineLis.markseqO(1)
OnlineLis.pushseqO(log n)
OnlineLis.reconstructseqO(n), O(n) memory
OnlineLis.undo_toseqO(1) amortized per undone push
Onlygraph
Only.deggraphO(deg u in g)
Only.outgraphO(1) to make, O(1) per arc of g walked
Only.transposegraphO(n + m)
Opalgebra
Op.opalgebra
Orderingalgebra
Pairpair
Pair.atpairO(1)
Pair.newpairO(1)
Pair.otherpairO(1)
Palindromesstrings
Palindromes.countstringsO(n)
Palindromes.is_emptystringsO(1)
Palindromes.is_palindromestringsO(1)
Palindromes.lenstringsO(1)
Palindromes.longeststringsO(n)
Palindromes.longest_atstrings
Palindromes.longest_betweenstrings
PalindromicTreestrings
PalindromicTree.atstrings
PalindromicTree.containsstringsO(|word|)
PalindromicTree.diffstrings
PalindromicTree.distinctstringsO(1)
PalindromicTree.growstrings
PalindromicTree.last_statestringsO(1)
PalindromicTree.lenstringsO(1)
PalindromicTree.linkstrings
PalindromicTree.min_palindrome_partitionstringsO(n log n)
PalindromicTree.newstringsO(|A|)
PalindromicTree.occ_countsstrings
PalindromicTree.ofstringsO(|s| * |A|) memory, O(|s|) amortized time
PalindromicTree.pal_lenstrings
PalindromicTree.popstringsO(1) amortized
PalindromicTree.pushstrings
PalindromicTree.push_frontstringsO(1) amortized
PalindromicTree.series_linkstrings
PalindromicTree.sizestrings
PalindromicTree.stepstrings
ParityDsudsu
ParityDsu.consistentdsuO(1)
ParityDsu.diffdsuO(log n)
ParityDsu.finddsuO(log n)
ParityDsu.markdsuO(1)
ParityDsu.newdsuO(n); three [V] arrays
ParityDsu.samedsuO(log n)
ParityDsu.sizedsuO(log n)
ParityDsu.undo_todsuO(1) per undone unite
ParityDsu.unitedsuO(log n), plus one log entry when it merges or contradicts
ParityDsu<V>.markwindow
ParityDsu<V>.undo_towindow
Pathsgraph
Paths.arcsgraphO(path length)
Paths.getgraphO(1) dense, O(1) expected hashed
Paths.itergraphO(1) to make, O(1) per item
Paths.pathgraphO(path length)
Paths.reachedgraphO(1)
Paths.tightgraphO(n + m)
PermKindtree
PermNodetree
PermTreetree
PermTree.leaftreeO(1)
PermTree.lefttreeO(1)
PermTree.newtreeO(n)
PermTree.nodetreeO(1)
PermTree.righttreeO(1)
PermTree.spantreeO(1)
PermTree.valstreeO(1)
PersistentArraypersistent
PersistentArray.basepersistentO(1)
PersistentArray.build_listpersistent
PersistentArray.getpersistentO(log n)
PersistentArray.newpersistentO(n) time and memory for n = |D|
PersistentArray.push_nodepersistent
PersistentArray.setpersistentO(log n) time and memory
PersistentArray.set_recpersistent
PersistentDsudsu
PersistentDsu.basedsuO(1)
PersistentDsu.builddsu
PersistentDsu.finddsuO(log² n)
PersistentDsu.getdsu
PersistentDsu.newdsuO(n)
PersistentDsu.putdsu
PersistentDsu.reservedsuO(nodes)
PersistentDsu.root_orddsu
PersistentDsu.samedsuO(log² n)
PersistentDsu.sizedsuO(log² n)
PersistentDsu.unitedsuO(log² n) time and O(log n) memory
PersistentLazySegTreepersistent
PersistentLazySegTree.allpersistentO(1)
PersistentLazySegTree.applypersistentO(log n) time and memory
PersistentLazySegTree.apply_recpersistent
PersistentLazySegTree.basepersistentO(1)
PersistentLazySegTree.build_listpersistent
PersistentLazySegTree.foldpersistentO(log n)
PersistentLazySegTree.fold_recpersistent
PersistentLazySegTree.getpersistentO(log n)
PersistentLazySegTree.newpersistentO(n) time and memory with a: or fill:, O(1) otherwise, for n = |D|
PersistentLazySegTree.push_nodepersistent
PersistentLazySegTree.setpersistentO(log n) time and memory
PersistentLazySegTree.set_recpersistent
PersistentLazySegTree.taggedpersistent
PersistentSegTreepersistent
PersistentSegTree.allpersistentO(1)
PersistentSegTree.basepersistentO(1)
PersistentSegTree.build_listpersistent
PersistentSegTree.diff_kthpersistentO(log n)
PersistentSegTree.foldpersistentO(log n)
PersistentSegTree.fold_recpersistent
PersistentSegTree.getpersistentO(log n)
PersistentSegTree.left_whilepersistentO(log n) calls of ok
PersistentSegTree.lwpersistent
PersistentSegTree.newpersistentO(n) time and memory with a: or fill:, O(1) otherwise, for n = |D|
PersistentSegTree.push_nodepersistent
PersistentSegTree.reservepersistentO(nodes)
PersistentSegTree.right_whilepersistentO(log n) calls of ok
PersistentSegTree.rwpersistent
PersistentSegTree.setpersistentO(log n) time and memory
PersistentSegTree.set_recpersistent
PersistentSegTree.updatepersistentO(log n) time and memory, one call of f
PersistentSegTree.update_recpersistent
Plane3geometry
Plane3.distgeometryO(1)
Plane3.projectgeometryO(1)
Plane3.throughgeometryO(1)
PMultisetpersistent
PMultiset.cmppersistentO(log |D|)
PMultiset.countpersistentO(log |D|)
PMultiset.emptypersistentO(1)
PMultiset.withpersistentO(log |D|) time and memory
PMultiset.withoutpersistentO(log |D|) time and memory
Polypoly
Poly.atpolyO(1)
Poly.degpolyO(1) plus the number of stored trailing zeros
Poly.derivpolyO(n)
Poly.evalpolyO(n)
Poly.exppolyO(n log n)
Poly.from_intpolyO(1)
Poly.integralpolyO(n)
Poly.invpolyO(n log n)
Poly.is_zeropolyO(1) plus the number of stored trailing zeros
Poly.lenpolyO(1)
Poly.logpolyO(n log n)
Poly.newpolyO(n)
Poly.onepolyO(1)
Poly.powpolyO(n log n)
Poly.setpolyO(1), or O(i) when it grows
Poly.shiftpolyO(n log n)
Poly.sqrtpolyO(n log n + log^2 P)
Poly.transposed_mulpolyO((n + m) log(n + m))
Poly.truncatedpolyO(n)
Poly.xpolyO(1)
Poly.zeropolyO(1)
Poly<T>.addpoly
Poly<T>.divpoly
Poly<T>.mulpoly
Poly<T>.negpoly
Poly<T>.subpoly
PotentialDsudsu
PotentialDsu.componentsdsuO(1)
PotentialDsu.consistentdsuO(1)
PotentialDsu.diffdsuO(log n)
PotentialDsu.finddsuO(log n)
PotentialDsu.markdsuO(1)
PotentialDsu.newdsuO(n); three [V] arrays
PotentialDsu.samedsuO(log n)
PotentialDsu.sizedsuO(log n)
PotentialDsu.undo_todsuO(1) per undone unite
PotentialDsu.unitedsuO(log n), plus one log entry when it merges or contradicts
PotentialDsu<V>.markwindow
PotentialDsu<V>.undo_towindow
PreferredPathstree
PreferredPaths.accesstreeamortized O(log n) switches
PreferredPaths.newtreeO(n)
Prefixprefix
Prefix.allprefixO(1)
Prefix.cyclic_sumprefixO(1)
Prefix.fillingprefixO(|D|) time and space
Prefix.first_geprefixO(log |D|)
Prefix.first_gtprefixO(log |D|)
Prefix.foldprefixO(1)
Prefix.getprefixO(1)
Prefix.newprefixO(|D|) time and space
Prefix.of_cutsprefix
Prefix.prefixprefixO(1)
Prefix.suffixprefixO(1)
PrefixXorBasismatrix
PrefixXorBasis.containsmatrixO(62)
PrefixXorBasis.max_xormatrixO(62)
PrefixXorBasis.newmatrixO(1)
PrefixXorBasis.pushmatrixO(62) time and space
PrefixXorBasis.rankmatrixO(62)
PrimePowerCombmod
PrimePowerComb.choosemodO(log_p n)
PrimePowerComb.free_factmod
PrimePowerComb.newmodO(p^e) time and memory
PrimePowerComb.p_countmod
Ptgeometry
Pt.addgeometry
Pt.anglegeometryO(1)
Pt.chebyshevgeometryO(1)
Pt.crossgeometryO(1)
Pt.cross128geometryO(1)
Pt.distgeometryO(1)
Pt.dist2geometryO(1)
Pt.dist2_128geometryO(1)
Pt.dotgeometryO(1)
Pt.dot128geometryO(1)
Pt.lengeometryO(1)
Pt.manhattangeometryO(1)
Pt.mulgeometry
Pt.neggeometry
Pt.norm2geometryO(1)
Pt.norm2_128geometryO(1)
Pt.perpgeometryO(1)
Pt.perp_cwgeometryO(1)
Pt.showgeometry
Pt.subgeometry
Pt.to_vecgeometryO(1)
Pt.unit_dirgeometryO(log max(|x|, |y|))
Pt3geometry
Pt3.addgeometry
Pt3.chebyshevgeometryO(1)
Pt3.crossgeometryO(1)
Pt3.distgeometryO(1)
Pt3.dist2geometryO(1)
Pt3.dotgeometryO(1)
Pt3.dot128geometryO(1)
Pt3.lengeometryO(1)
Pt3.manhattangeometryO(1)
Pt3.mulgeometry
Pt3.neggeometry
Pt3.norm2geometryO(1)
Pt3.norm2_128geometryO(1)
Pt3.showgeometry
Pt3.subgeometry
Pt3.to_vec3geometryO(1)
RangeKthpersistent
RangeKth.count_inpersistentO(log n)
RangeKth.count_lepersistentO(log n)
RangeKth.count_ltpersistentO(log n)
RangeKth.count_prefixpersistent
RangeKth.incpersistent
RangeKth.kthpersistentO(log n)
RangeKth.lower_valpersistent
RangeKth.newpersistentO(n log n) time and memory for n = a.len
RangeKth.upper_valpersistent
Ratiomath
Ratio.absmathO(1)
Ratio.addmath
Ratio.ceilmathO(1)
Ratio.divmath
Ratio.floormathO(1)
Ratio.from_intmathO(1)
Ratio.invmathO(1)
Ratio.ltmath
Ratio.mulmath
Ratio.negmath
Ratio.newmathO(log min(|p|, |q|))
Ratio.showmath
Ratio.submath
Rebasedseq
Rectgeometry
Rect.areageometryO(1)
Rect.containsgeometryO(1)
Rect.intersectgeometryO(1)
Rect.is_emptygeometryO(1)
RelaxedConvolventt
RelaxedConvolve.newnttO(1)
RelaxedConvolve.pushnttO(log^2 k) amortized
Revseq
Rev.srcseqO(1)
Reversiblealgebra
Reversible.revalgebra
Reweightedgraph
Ringseq
Ring.fromseqO(1) per step
Ring.maximalseqO(n) pushes and pops on state
Ring.minimalseqO(n) pushes and pops on state
Ring.nextseqO(1)
Ring.prevseqO(1)
Ring.spanseqO(1)
Ring.stepseqO(1)
Ring.windowsseqO(1) per window
RingRangeseq
RingRange.containsseqO(1)
RingRange.endseqO(1)
RingRange.keysseqO(1) to make, O(1) per step
RingRange.lenseqO(1)
RingRange.startseqO(1)
RingSliceseq
RingSlice.endseqO(1)
RingSlice.keysseqO(1) to make, O(1) per step
RingSlice.lenseqO(1)
RingSlice.rangeseqO(1)
RingSlice.startseqO(1)
Rngrand
Rng.chancerandO(1)
Rng.floatrandO(1)
Rng.intrandO(1)
Rng.newrandO(1)
Rng.nextrandO(1)
Rng.permrandO(n)
Rng.pickrandO(1)
Rng.samplerandO(|from|)
Rng.shufflerandO(n)
RollbackArraydsu
RollbackArray.getdsuO(1)
RollbackArray.markdsuO(1)
RollbackArray.newdsuO(n) calls of init, for n = D.count
RollbackArray.setdsuO(1), plus one log entry
RollbackArray.undo_todsuO(1) per undone set
RollingHashstrings
RollingHash.allstringsO(1)
RollingHash.combinestringsO(1) amortized (the power table grows past len on demand)
RollingHash.concatstringsO(|parts|) amortized
RollingHash.eq_substrings
RollingHash.getstringsO(1)
RollingHash.hash_ofstringsO(|seq|)
RollingHash.is_emptystringsO(1)
RollingHash.lcpstringsO(log n)
RollingHash.lcp_withstringsO(log min(|self| - a, |other| - b))
RollingHash.lcsstringsO(log n)
RollingHash.lenstringsO(1)
RollingHash.newstrings
RollingHash.popstringsO(1)
RollingHash.pushstringsO(1) amortized
RollingHash.raw_slicestrings
RollingHash.slicestringsO(1)
RollingHash61strings
RollingHash61.allstringsO(1)
RollingHash61.combinestringsO(1) amortized (the power table grows past len on demand)
RollingHash61.getstringsO(1)
RollingHash61.is_emptystringsO(1)
RollingHash61.lcpstringsO(log n)
RollingHash61.lcp_withstringsO(log min(|self| - a, |other| - b))
RollingHash61.lcsstringsO(log n)
RollingHash61.lenstringsO(1)
RollingHash61.newstringsO(n)
RollingHash61.popstringsO(1)
RollingHash61.pushstringsO(1) amortized
RollingHash61.slice61strings
Rootedtree
Rooted.abovetreeO(n) calls of lift and finish, O(n) calls of op
Rooted.ancestortreeO(log n)
Rooted.ancestorstreeO(1) per vertex, O(depth(v)) in all
Rooted.apply_pathtreeO(log² n)
Rooted.belowtreeO(1)
Rooted.buildtree
Rooted.centroidtreeO(depth)
Rooted.centroidstreeO(depth)
Rooted.chaintreeO(1)
Rooted.chainstreeO(log n) ranges
Rooted.child_arcstreeO(1) per child
Rooted.childrentreeO(1) to start, O(1) per child
Rooted.depthtreeO(1)
Rooted.diametertreeO(n)
Rooted.disttreeO(log n)
Rooted.downtreeO(n) calls of f
Rooted.euler_tourtreeO(1) per item
Rooted.eventstreeO(n)
Rooted.excl_foldtreeO(k) calls of f and of op, O(k) memory
Rooted.farthesttreeO(log n): at most four dist calls
Rooted.fold_pathtreeO(log² n) with one structure
Rooted.foresttreeO(n + m)
Rooted.from_parentstreeO(n)
Rooted.is_anctreeO(1)
Rooted.jumptreeO(log n)
Rooted.jump_whiletreeO(log² n) calls of pred
Rooted.layerstreeO(n)
Rooted.lcatreeO(log n)
Rooted.lighttreeO(children)
Rooted.long_pathstreeO(n)
Rooted.lowertreeO(1)
Rooted.meettreeO(log n)
Rooted.newtreeO(n + m) for m listed arcs, without recursion
Rooted.on_pathtreeO(log n)
Rooted.parenttreeO(1)
Rooted.pathtreeO(log n + |path|)
Rooted.postreeO(1)
Rooted.preordertreeO(size(v)), less when pruned
Rooted.reordertreeO(n)
Rooted.reroottreeO(n) calls of lift and finish, O(n) calls of op
Rooted.root_oftreeO(log n)
Rooted.rootstreeO(1) to make, O(1) per root
Rooted.shapestreeO(n log n)
Rooted.sizetreeO(1)
Rooted.subtreeO(1)
Rooted.sub_attreeO(log n)
Rooted.subtreetreeO(size(v))
Rooted.subtree_sizestreeO(1); a view of the stored sizes
Rooted.toptreeO(1)
Rooted.tourtreeO(1) to make, O(n) to walk
Rooted.try_from_parentstreeO(n)
Rooted.uptreeO(n) calls of lift, op and finish
Rooted.up_arctreeO(1)
Rooted.virtualtreeO(k log k + k log n) for k keys
Rooted.wtreeO(1)
Ropelazy
Rope.applylazyO(log n) expected
Rope.downlazy
Rope.emitlazy
Rope.findlazy
Rope.getlazyO(log n) expected
Rope.joinlazy
Rope.newlazyO(|D|)
Rope.pulllazy
Rope.reverselazyO(log n) expected
Rope.setlazyO(log n) expected
Rope.sizelazy
Rope.splitlazy
Rope.tag_nodelazy
Rope.to_arraylazyO(|D|)
SegTreesegtree
SegTree.allsegtreeO(1)
SegTree.applysegtreeO(log |D|)
SegTree.apply_allsegtreeO(1) amortized when the tags commute, else O(|D|)
SegTree.atsegtreeO(log |D|) per write
SegTree.buildsegtree
SegTree.build_lazysegtree
SegTree.clearsegtreeO(|D|)
SegTree.foldsegtreeO(log |D|)
SegTree.getsegtreeO(1); O(log |D|) on a tree with act:
SegTree.left_whilesegtreeO(log |D|)
SegTree.monoidsegtreeO(1)
SegTree.newsegtreeO(|D|); O(1) with over:
SegTree.ofsegtreeO(|D|), calling f once per position in key order
SegTree.opensegtree
SegTree.pullsegtree
SegTree.pull_nodesegtree
SegTree.pushsegtree
SegTree.putsegtree
SegTree.refreshsegtreeO(log |D|) plus one call of f
SegTree.right_whilesegtreeO(log |D|)
SegTree.setsegtreeO(log |D|)
SegTree.try_foldsegtreeO(log |D|)
SegTree.updatesegtreeO(log |D|) plus one call of f
SegTree.walksegtreeO(log |D|)
SegTree2Dsegtree
SegTree2D.allsegtreeO(1)
SegTree2D.foldsegtreeO(log |R| * log |C|)
SegTree2D.fold_rowsegtree
SegTree2D.getsegtreeO(1)
SegTree2D.newsegtreeO(|R| * |C|)
SegTree2D.setsegtreeO(log |R| * log |C|)
SegTree2D.updatesegtreeO(log |R| * log |C|) plus one call of f
Selectivealgebra
Semigroupalgebra
SemiRelaxedConvolventt
SemiRelaxedConvolve.newnttO(b.len)
SemiRelaxedConvolve.pushnttO(log^2 k) amortized
Semiringalgebra
Settleheap
Settle.betterheap
Settle.getheapO(1) expected
Settle.offerheapO(log n) amortized, n the offers so far
Settle.popheapO(log n) amortized, n the offers so far
Settle.settledheapO(1) expected
Settle.sift_downheap
Settle.sift_upheap
Sievemath
Sieve.div_count_tablemathO(n)
Sieve.div_sum_tablemathO(n)
Sieve.divisorsmathO(log x) to start, O(1) per divisor
Sieve.factormathO(log x)
Sieve.is_primemathO(1)
Sieve.mobiusmathO(log x)
Sieve.mobius_tablemathO(n)
Sieve.newmathO(n) time and memory
Sieve.phimathO(log x)
Sieve.phi_tablemathO(n)
Signmath
Sliceseq
Slice.is_emptyseqO(1)
Slice.iterseqO(1) per step
Slice.keysseqO(1)
Slice.lenseqO(1)
SortedBagbag
SortedBag.absorbbagO(min(n, m) log(n + m)) expected
SortedBag.addbagO(log n) expected
SortedBag.add_manybagO(log n) expected, independent of c
SortedBag.add_uniquebag
SortedBag.clearbagO(1)
SortedBag.containsbagO(log n) expected
SortedBag.countbagO(log n) expected
SortedBag.count_ofbagO(1)
SortedBag.cursor_atbagO(log n) expected
SortedBag.cursor_firstbagO(log n) expected
SortedBag.cursor_gebagO(log n) expected
SortedBag.cursor_gtbagO(log n) expected
SortedBag.cursor_lastbagO(log n) expected
SortedBag.cursor_lebagO(log n) expected
SortedBag.cursor_ltbagO(log n) expected
SortedBag.distinctbagO(1)
SortedBag.drainbagO(k log n) expected for k removed elements
SortedBag.drain_rangebagO(log n + k) expected for k removed
SortedBag.entriesbagO(1) amortized per step
SortedBag.entries_revbagO(1) amortized per step
SortedBag.erase_atbag
SortedBag.firstbagO(1)
SortedBag.first_truebagO(log n) expected calls of ok
SortedBag.hi_okbag
SortedBag.insert_atbag
SortedBag.is_emptybagO(1)
SortedBag.joinbagO(log n) expected
SortedBag.key_ofbagO(1)
SortedBag.lastbagO(1)
SortedBag.last_truebagO(log n) expected calls of ok
SortedBag.lenbagO(1)
SortedBag.lo_okbag
SortedBag.make_nodebag
SortedBag.mergebag
SortedBag.move_outbag
SortedBag.newbagO(1)
SortedBag.next_cursorbagO(1) amortized, O(log n) worst case
SortedBag.nthbagO(log n) expected
SortedBag.ofbagO(n log n) expected
SortedBag.pop_firstbagO(log n) expected
SortedBag.pop_lastbagO(log n) expected
SortedBag.prev_cursorbagO(1) amortized, O(log n) worst case
SortedBag.pullbag
SortedBag.rangebagO(1) to make; see SortedRange for each query
SortedBag.range_eachbag
SortedBag.range_each_revbag
SortedBag.range_firstbag
SortedBag.range_lastbag
SortedBag.range_lenbag
SortedBag.rankbagO(log n) expected
SortedBag.rank_lebag
SortedBag.refreshbag
SortedBag.removebagO(log n) expected
SortedBag.remove_allbagO(log n) expected
SortedBag.reservebagO(cap) when the pool grows, O(1) otherwise
SortedBag.split_atbagO(log n + s log n) expected, s the smaller side's distinct keys
SortedBag.split_ltbag
SortedBag.sub_ofbag
SortedBag.sumbagO(n)
SortedBag.takebagO(1)
SortedBag.take_firstbagO(log n) expected
SortedBag.to_listbagO(n)
SortedMapbag
SortedMap.absorbbagO(min(n, m) log(n + m)) expected
SortedMap.atbag
SortedMap.clearbagO(1)
SortedMap.containsbagO(log n) expected
SortedMap.drainbagO(k log n) expected for k removed entries
SortedMap.each_revbagO(1) amortized per step
SortedMap.entrybag
SortedMap.firstbagO(1)
SortedMap.first_gebagO(log n) expected
SortedMap.first_gtbagO(log n) expected
SortedMap.first_truebagO(log n) expected calls of ok
SortedMap.getbagO(log n) expected
SortedMap.is_emptybagO(1)
SortedMap.itemsbagO(1) to make, O(1) amortized per step
SortedMap.joinbagO(log n) expected
SortedMap.keysbagO(1) to make, O(1) amortized per step
SortedMap.lastbagO(1)
SortedMap.last_lebagO(log n) expected
SortedMap.last_ltbagO(log n) expected
SortedMap.last_truebagO(log n) expected calls of ok
SortedMap.lenbagO(1)
SortedMap.newbagO(1)
SortedMap.nthbagO(log n) expected
SortedMap.pop_firstbagO(log n) expected
SortedMap.pop_lastbagO(log n) expected
SortedMap.rankbagO(log n) expected
SortedMap.removebagO(log n) expected
SortedMap.reservebagO(cap) when the pool grows, O(1) otherwise
SortedMap.setbagO(log n) expected
SortedMap.split_atbagO(log n) expected
SortedMap.takebagO(1)
SortedMap.valuesbagO(1) to make, O(1) amortized per step
SortedRangebag
SortedRange.eachbagO(log n + k) expected for k keys visited
SortedRange.firstbagO(log n) expected
SortedRange.is_emptybagO(log n) expected
SortedRange.lastbagO(log n) expected
SortedRange.lenbagO(log n) expected
SortedRange.revbagO(log n + k) expected for k keys visited
SortedSetbag
SortedSet.absorbbagO(min(n, m) log(n + m)) expected
SortedSet.addbagO(log n) expected
SortedSet.clearbagO(1)
SortedSet.containsbagO(log n) expected
SortedSet.drainbagO(k log n) expected for k removed keys
SortedSet.eachbagO(1) amortized per step
SortedSet.each_revbagO(1) amortized per step
SortedSet.firstbagO(1)
SortedSet.first_truebagO(log n) expected calls of ok
SortedSet.is_emptybagO(1)
SortedSet.joinbagO(log n) expected
SortedSet.lastbagO(1)
SortedSet.last_truebagO(log n) expected calls of ok
SortedSet.lenbagO(1)
SortedSet.newbagO(1)
SortedSet.nthbagO(log n) expected
SortedSet.ofbagO(n log n) expected
SortedSet.pop_firstbagO(log n) expected
SortedSet.pop_lastbagO(log n) expected
SortedSet.rangebagO(1) to make; see SortedRange for each query
SortedSet.range_eachbag
SortedSet.range_each_revbag
SortedSet.range_firstbag
SortedSet.range_lastbag
SortedSet.range_lenbag
SortedSet.rankbagO(log n) expected
SortedSet.removebagO(log n) expected
SortedSet.reservebagO(cap) when the pool grows, O(1) otherwise
SortedSet.setbagO(log n) expected
SortedSet.split_atbagO(log n + s log n) expected, s the smaller side's size
SortedSet.sumbagO(log n) expected
SortedSet.takebagO(1)
SortedSet.to_listbagO(n)
SosOverntt
SparseFenwick2Dfenwick
SparseFenwick2D.addfenwickO(log^2 n)
SparseFenwick2D.add_pointfenwickO(1) amortized
SparseFenwick2D.buildfenwickO(n log n) for n registered points; memory O(n log n)
SparseFenwick2D.cornerfenwick
SparseFenwick2D.foldfenwickO(log^2 n)
SparseFenwick2D.newfenwickO(1)
SparseIntervalMapinterval
SparseIntervalMap.assignintervalO((1 + removed) log runs) amortized
SparseIntervalMap.eachintervalO(1) per run
SparseIntervalMap.each_revintervalO(1) per run
SparseIntervalMap.getintervalO(log runs)
SparseIntervalMap.merge_atinterval
SparseIntervalMap.newintervalO(1)
SparseIntervalMap.rangeintervalO(log runs + k) for k pieces
SparseIntervalMap.run_atintervalO(log runs)
SparseIntervalMap.runsintervalO(1)
SparseIntervalMap.splitinterval
SparseIntervalMap.updateintervalO((1 + touched) log runs)
SparseIntervalSetinterval
SparseIntervalSet.addintervalO((1 + merged) log runs) amortized
SparseIntervalSet.containsintervalO(log runs)
SparseIntervalSet.coveredintervalO(1)
SparseIntervalSet.eachintervalO(1) per interval
SparseIntervalSet.newintervalO(1)
SparseIntervalSet.next_gapintervalO(log runs)
SparseIntervalSet.removeintervalO((1 + split) log runs) amortized
SparseIntervalSet.runsintervalO(1)
SparseSetmarks
SparseSet.addmarksO(1)
SparseSet.clearmarksO(1)
SparseSet.containsmarksO(1)
SparseSet.eachmarksO(len)
SparseSet.is_emptymarksO(1)
SparseSet.lenmarksO(1)
SparseSet.newmarksO(|D|)
SparseSet.removemarksO(1)
SparseTablesparse
SparseTable.allsparseO(1)
SparseTable.foldsparseO(1)
SparseTable.getsparseO(1)
SparseTable.newsparseO(|D| log |D|) time and memory, op called O(|D| log |D|) times
SparseTable.try_foldsparseO(1)
SparseTable2Dsparse
SparseTable2D.atsparse
SparseTable2D.foldsparseO(1)
SparseTable2D.getsparseO(1)
SparseTable2D.newsparseO(|R| |C| log |R| log |C|) time and memory
SparseTable2D.try_foldsparseO(1)
Stepdp
Step.prunedpO(1)
SubproductTreepoly
SubproductTree.evalpolyO((deg f + m) log^2 m)
SubproductTree.eval_transposedpolyO(m log^2 m)
SubproductTree.interpolatepolyO(m log^2 m)
SubproductTree.newpolyO(m log^2 m) time, O(m log m) space
SubseqStepseq
SubseqStep.pruneseqO(1)
Subsetsubset
Subset.complementsubsetO(1)
Subset.containssubsetO(1)
Subset.emptysubsetO(1)
Subset.firstsubsetO(1)
Subset.fullsubsetO(1)
Subset.itemssubsetO(1) per member
Subset.lensubsetO(1)
Subset.setsubsetO(1)
Subset.shiftedsubsetO(1)
Subset.singlesubsetO(1)
Subset.subsetssubsetO(1) per subset, 2^s.len subsets
Subset.supersetssubsetO(1) per superset, 2^(|B| - s.len) supersets
Subset.withsubsetO(1)
Subset.withoutsubsetO(1)
Subset<B>.bitandsubset
Subset<B>.bitorsubset
Subset<B>.bitxorsubset
Subset<B>.subsubset
SuffixArraystrings
SuffixArray.arg_minstrings
SuffixArray.comparestringsO(1)
SuffixArray.countstringsO(|pat| log n)
SuffixArray.distinctstringsO(n)
SuffixArray.find_allstringsO(|pat| log n + occurrences)
SuffixArray.is_emptystringsO(1)
SuffixArray.kth_distinctstringsO(log n)
SuffixArray.lcp_betweenstringsO(1)
SuffixArray.lcp_of_ranksstringsO(1)
SuffixArray.lcp_rangestringsO(log n)
SuffixArray.lenstringsO(1)
SuffixArray.newstringsO(n) for Str and small integer alphabets, O(n log n) otherwise
SuffixArray.rank_rangestringsO(|pat| log n)
SuffixArray.splitstringsO(1)
SuffixAutomatonstrings
SuffixAutomaton.add_empty_statestrings
SuffixAutomaton.add_wordstringsO(|word|) amortized
SuffixAutomaton.clone_statestrings
SuffixAutomaton.containsstringsO(|word|)
SuffixAutomaton.distinctstringsO(states)
SuffixAutomaton.endpos_treestringsO(states)
SuffixAutomaton.findstrings
SuffixAutomaton.first_posstrings
SuffixAutomaton.kth_substringstringsO(states * |A|)
SuffixAutomaton.lcsstrings
SuffixAutomaton.lenstringsO(1)
SuffixAutomaton.linkstrings
SuffixAutomaton.longeststrings
SuffixAutomaton.newstringsO(|A|)
SuffixAutomaton.occ_countsstrings
SuffixAutomaton.ofstringsO(|s| * |A|) memory, O(|s|) amortized time
SuffixAutomaton.pushstrings
SuffixAutomaton.resetstringsO(1)
SuffixAutomaton.rootstringsO(1)
SuffixAutomaton.shorteststrings
SuffixAutomaton.statesstringsO(states)
SuffixAutomaton.stepstrings
SuffixAutomaton.topo_orderstrings
SuffixTreeEdgestrings
Sweepwindow
Sweep.movewindowO(|dl| + |dr|) pushes and pops, where dl and dr are the moves of the two ends
Sweep.newwindowO(1), plus start.len pushes when start is given
Sweep.rangewindowO(1)
SweepAddprefix
SweepAdd.addprefixO(1)
SweepAdd.advanceprefixO(1)
SweepAdd.currentprefixO(1)
SweepAdd.newprefixO(|D|) time and space
Targetgraph
Target.tographO(1)
TimeSteptimetree
TimeTreetimetree
TimeTree.add_intervaltimetreeO(log q)
TimeTree.add_rangetimetreeO(log q)
TimeTree.emit_dfstimetree
TimeTree.eventtimetreeO(1)
TimeTree.linktimetree
TimeTree.newtimetreeO(q) time and memory
TimeTree.runtimetreeO(q + m log q) callback calls for m scheduled intervals, O(log q) extra stack
TimeTree.run_nodetimetree
TimeTree.stepstimetreeO(q + m log q) time and memory for m scheduled intervals
TimeTree.walktimetreeO(1) amortized per step, O(log q) extra stack
Trackwindow
Track.popwindow
Track.pushwindow
Trackedwindow
Tracked.popwindowone call of remove
Tracked.pushwindowone call of add
Tracked.statewindowO(1)
Triestrings
Trie.addstrings
Trie.clearstringsO(1)
Trie.containsstringsO(|word|)
Trie.countstrings
Trie.count_lessstringsO(|word| * |A|)
Trie.count_prefixstrings
Trie.ends_atstrings
Trie.findstrings
Trie.is_emptystringsO(1)
Trie.kthstringsO(depth * |A|)
Trie.lenstringsO(1)
Trie.newstringsO(|A|)
Trie.pass_atstrings
Trie.removestrings
Trie.rootstringsO(1)
Trie.stepstrings
TwoSatgraph
TwoSat.add_eqgraphO(1) amortized
TwoSat.add_orgraphO(1) amortized
TwoSat.add_xorgraphO(1) amortized
TwoSat.at_most_onegraphO(k) amortized
TwoSat.clausegraph
TwoSat.impliesgraphO(1) amortized
TwoSat.mustgraphO(1) amortized
TwoSat.newgraphO(|X|)
TwoSat.solvegraphO(|X| + clauses)
Undowindow
Undo.markwindow
Undo.undo_towindow
Undoingwindow
Undoing.popwindowO(log n) applications of add amortized
Undoing.pushwindowO(1) applications of add amortized
Undoing.push_entrywindow
Undoing.statewindowO(1)
Vecgeometry
Vec.addgeometry
Vec.anglegeometryO(1)
Vec.crossgeometryO(1)
Vec.distgeometryO(1)
Vec.dist2geometryO(1)
Vec.divgeometry
Vec.dotgeometryO(1)
Vec.from_anglegeometryO(1)
Vec.lengeometryO(1)
Vec.mulgeometry
Vec.neggeometry
Vec.norm2geometryO(1)
Vec.perpgeometryO(1)
Vec.perp_cwgeometryO(1)
Vec.rotgeometryO(1)
Vec.subgeometry
Vec.unitgeometryO(1)
Vec3geometry
Vec3.addgeometry
Vec3.crossgeometryO(1)
Vec3.distgeometryO(1)
Vec3.dist2geometryO(1)
Vec3.divgeometry
Vec3.dotgeometryO(1)
Vec3.lengeometryO(1)
Vec3.mulgeometry
Vec3.neggeometry
Vec3.norm2geometryO(1)
Vec3.rotgeometryO(1)
Vec3.subgeometry
Vec3.unitgeometryO(1)
Versionpersistent
VirtualTreetree
Visitgraph
Walkgraph
Walk.verticesgraphO(1) to make, O(1) per vertex
WaveletMatrixsegtree
WaveletMatrix.belowsegtree
WaveletMatrix.count_insegtreeO(log V)
WaveletMatrix.count_ltsegtreeO(log V)
WaveletMatrix.kthsegtreeO(log V)
WaveletMatrix.newsegtreeO(|D| log V) time and memory
WaveletMatrix.next_valsegtreeO(log V)
WaveletMatrix.onessegtree
WaveletMatrix.prev_valsegtreeO(log V)
WaveletMatrix.quantile_sumsegtreeO(log V)
WaveletMatrix.ranksegtreeO(log V)
Weightedgraph
Weighted.wgraphO(1) plus the cost of f under weighted
WeightedNextgraph
Windowwindow
Window.allwindowO(1)
Window.drop_frontwindow
Window.lenwindowO(1)
Window.newwindowO(1)
Window.popwindowO(1) amortized calls of op
Window.pushwindowO(1) amortized calls of op
Window.push_backwindow
Window<T, M>.popwindow
Window<T, M>.pushwindow
Wireio
Wire.askioO(|query|) plus the read of one T
Wire.newioO(1)
Word.revalgebra
Word.revtree
XorBasismatrix
XorBasis.addmatrixO(W)
XorBasis.basis_vecsmatrixO(W) time and space
XorBasis.containsmatrixO(W)
XorBasis.intersectmatrixO(W^2)
XorBasis.kthmatrixO(W^2)
XorBasis.max_xormatrixO(W)
XorBasis.mergematrixO(W * o.rank)
XorBasis.min_xormatrixO(W)
XorBasis.monoidmatrixO(W) (for the identity)
XorBasis.newmatrixO(W)
XorBasis.rankmatrixO(1)
XorBasis.reducematrixO(W)
XorTriebitset
XorTrie.addbitsetO(bits) time, up to bits new nodes
XorTrie.childbitset
XorTrie.clearbitsetO(1)
XorTrie.containsbitsetO(bits)
XorTrie.countbitsetO(bits)
XorTrie.count_xor_lessbitsetO(bits)
XorTrie.extreme_xorbitset
XorTrie.is_emptybitsetO(1)
XorTrie.kth_xorbitsetO(bits)
XorTrie.leafbitset
XorTrie.lenbitsetO(1)
XorTrie.max_xorbitsetO(bits)
XorTrie.mex_xorbitsetO(bits)
XorTrie.min_xorbitsetO(bits)
XorTrie.newbitsetO(1)
XorTrie.removebitsetO(bits)
XorTrie.reservebitsetO(nodes) time and space
XorTrie.walkbitset
XorTrie.xor_allbitsetO(1)

On this page