sparse
SparseTable<V, Int>(min, a): built in O(n log n) time and memory, fold is O(1).
Generated from spec/std/sparse.cp by cpl doc --format json.
SparseTable
pub struct SparseTable<D, T>(op: (T, T) -> T)SparseTable<V, Int>(min, a): built in O(n log n) time and memory, fold is O(1).
The operation must be associative and idempotent (op(a, a) == a): min, max, gcd,
&, |, or any custom (T, T) -> T — no identity is required because fold asserts
the range is non-empty and returns T directly. Sums are not idempotent; use Fenwick or prefix for those.
SparseTable.new
fn new(op: (T, T) -> T, a: [D]T) -> SparseTable<D, T>Build a sparse table for the idempotent, associative op over the values of a. Level k
holds the fold of every window of length 2^k, so any non-empty range is the fold of two
overlapping windows. The table copies a and keeps its domain D.
- cost: O(|D| log |D|) time and memory,
opcalled O(|D| log |D|) times - empty: an empty
abuilds an empty table; everyfoldon it traps,try_foldisNone - order: the table keeps the domain
Dofa - traps: never (a non-idempotent or non-associative
opgives unspecified folds; check withidempotent)
Examples:
SparseTable(min, [3, 1, 4]).fold(0..3) == 1
SparseTable.fold
fn fold(self, r: Range<D>) -> TThe fold of op over the positions of the non-empty range r, as two overlapping
power-of-two windows combined with one op call.
- cost: O(1)
- empty: traps; use
try_foldwhenrmay be empty - traps: when
ris empty or reaches outsideD
Examples:
SparseTable(max, [3, 1, 4]).fold(0..2) == 3SparseTable(min, [3, 1, 4]).fold(1..2) == 1
SparseTable.try_fold
fn try_fold(self, r: Range<D>) -> ?TThe fold of r like fold, or None when r is empty.
- cost: O(1)
- empty:
None - traps: when a non-empty
rreaches outsideD
Examples:
SparseTable(min, [3, 1, 4]).try_fold(1..1) == NoneSparseTable(min, [3, 1, 4]).try_fold(1..3) == Some(1)
SparseTable.get
fn get(self, i: D) -> TThe original value at position i (level 0 of the table).
- cost: O(1)
- traps: when
iis outsideD
Examples:
SparseTable(min, [3, 1, 4]).get(2) == 4
SparseTable.all
fn all(self) -> TThe fold of every position of D; fold(D.all).
- cost: O(1)
- empty: traps on an empty domain
- traps: when
Dis empty
Examples:
SparseTable(gcd, [4, 6, 10]).all == 2
DisjointSparseTable
pub struct DisjointSparseTable<D, T>(op: (T, T) -> T)Disjoint sparse table: O(n log n) build and memory, O(1) range fold for ANY associative
operation — no idempotence and no inverse required (matrix products, Mod<P> products,
MaxSub, string concatenation). Asserts not r.is_empty.
DisjointSparseTable.new
fn new(op: (T, T) -> T, a: [D]T) -> DisjointSparseTable<D, T>Build a disjoint sparse table for the associative op over a. Each level splits the domain
into blocks and stores folds outward from each block's middle, so a range is answered by
combining one suffix fold and one prefix fold; no idempotence, identity or inverse is needed.
- cost: O(|D| log |D|) time and memory,
opcalled O(|D| log |D|) times - empty: an empty
abuilds an empty table; everyfoldon it traps,try_foldisNone - order: the table keeps the domain
Dofa; folds run in domain order - traps: never (a non-associative
opgives unspecified folds)
Examples:
DisjointSparseTable((a, b) => a + b, [3, 1, 4]).fold(0..3) == 8
DisjointSparseTable.fold
fn fold(self, r: Range<D>) -> TThe fold of op over the non-empty range r, left to right in domain order, so a
non-commutative op sees its operands in position order.
- cost: O(1), at most one
opcall - empty: traps; use
try_foldwhenrmay be empty - traps: when
ris empty or reaches outsideD
Examples:
DisjointSparseTable((a, b) => a + b, [3, 1, 4]).fold(1..3) == 5DisjointSparseTable((a, b) => a, [7, 8, 9]).fold(1..3) == 8
DisjointSparseTable.try_fold
fn try_fold(self, r: Range<D>) -> ?TThe fold of r like fold, or None when r is empty.
- cost: O(1)
- empty:
None - traps: when a non-empty
rreaches outsideD
Examples:
DisjointSparseTable((a, b) => a + b, [3, 1, 4]).try_fold(2..2) == NoneDisjointSparseTable((a, b) => a + b, [3, 1, 4]).try_fold(0..2) == Some(4)
DisjointSparseTable.get
fn get(self, i: D) -> TThe original value at position i.
- cost: O(1)
- traps: when
iis outsideD
Examples:
DisjointSparseTable((a, b) => a + b, [3, 1, 4]).get(0) == 3
DisjointSparseTable.all
fn all(self) -> TThe fold of every position of D, left to right; fold(D.all).
- cost: O(1)
- empty: traps on an empty domain
- traps: when
Dis empty
Examples:
DisjointSparseTable((a, b) => a + b, [3, 1, 4]).all == 8
SparseTable2D
pub struct SparseTable2D<R, C, T>(op: (T, T) -> T)O(|R| * |C| * log |R| * log |C|) build and memory; O(1) rectangle fold for any associative,
idempotent operation (min, max, gcd, &, |).
SparseTable2D.at
fn at(self, kr: Int, kc: Int, i: Int, j: Int) -> IntSparseTable2D.new
fn new(op: (T, T) -> T, a: [R, C]T) -> SparseTable2D<R, C, T>Build a 2-D sparse table for the idempotent, associative op over the grid a: one
SparseTable level per power-of-two row height and column width. Keeps the domains R, C.
- cost: O(|R| |C| log |R| log |C|) time and memory
- empty: an empty grid builds an empty table; every
foldon it traps - order: the table keeps the domains
RandCofa - traps: never (a non-idempotent
opgives unspecified folds)
Examples:
SparseTable2D(max, [2, 2] (r, c) => r * 2 + c).fold(0..2, 0..2) == 3
SparseTable2D.fold
fn fold(self, rows: Range<R>, cols: Range<C>) -> TThe fold of op over the rectangle rows by cols, both non-empty: four overlapping
power-of-two blocks combined with op.
- cost: O(1)
- empty: traps when either range is empty; use
try_fold - traps: when either range is empty or reaches outside its domain
Examples:
SparseTable2D(min, [2, 2] (r, c) => r * 2 + c).fold(1..2, 0..2) == 2
SparseTable2D.try_fold
fn try_fold(self, rows: Range<R>, cols: Range<C>) -> ?TThe rectangle fold like fold, or None when rows or cols is empty.
- cost: O(1)
- empty:
Nonewhen either range is empty - traps: when a range reaches outside its domain on a non-empty rectangle
Examples:
SparseTable2D(min, [2, 2] (r, c) => r * 2 + c).try_fold(0..2, 1..1) == NoneSparseTable2D(min, [2, 2] (r, c) => r * 2 + c).try_fold(0..2, 1..2) == Some(1)
SparseTable2D.get
fn get(self, r: R, c: C) -> TThe original cell value a[r, c].
- cost: O(1)
- traps: when
ris outsideRorcis outsideC
Examples:
SparseTable2D(min, [2, 2] (r, c) => r * 2 + c).get(1, 0) == 2
LinearRmq
pub struct LinearRmq<D, T>(before: (T, T) -> Bool)O(|D|) build and memory; O(1) range min/max query via block-of-64 bitmask RMQ (Four Russians). Useful for O(1) LCA and memory-tight static RMQ where O(n log n) space is too large.
LinearRmq.better
fn better(self, i: Int, j: Int) -> IntLinearRmq.in_block
fn in_block(self, l: Int, r: Int) -> IntLinearRmq.new
fn new(a: [D]T, before: (T, T) -> Bool = (x, y) => x < y) -> LinearRmq<D, T>Build a linear-space range-best structure over a, where before(x, y) means x is better
than y (default <, so the best is the minimum). Blocks of 64 positions carry a sparse
table over block bests and an in-block bitmask stack, so queries never scan.
- cost: O(|D|) time and memory
- empty: an empty
abuilds an empty structure;argbestandbeston it trap - order: the structure keeps the domain
Dofa - traps: never (
beforemust be a strict weak order, or results are unspecified)
Examples:
LinearRmq([3, 1, 4]).best(0..3) == 1
LinearRmq.argbest
fn argbest(self, r: Range<D>) -> DThe position of the best element of the non-empty range r under before; the leftmost
when several are equally best (neither is before the other).
- cost: O(1)
- empty: traps
- ties: the first in key order
- traps: when
ris empty or reaches outsideD
Examples:
LinearRmq([3, 1, 1, 4]).argbest(0..4) == 1LinearRmq([3, 1, 4], before: (x, y) => x > y).argbest(0..3) == 2
LinearRmq.best
fn best(self, r: Range<D>) -> TThe value of the best element of the non-empty range r under before; a[argbest(r)].
- cost: O(1)
- empty: traps; use
try_bestwhenrmay be empty - ties: equal-best values are interchangeable; the value at the leftmost is returned
- traps: when
ris empty or reaches outsideD
Examples:
LinearRmq([3, 1, 4], before: (x, y) => x > y).best(0..3) == 4
LinearRmq.try_best
fn try_best(self, r: Range<D>) -> ?TThe value of the best element of r like best, or None when r is empty.
- cost: O(1)
- empty:
None - ties: the value at the leftmost equal-best position
- traps: when a non-empty
rreaches outsideD
Examples:
LinearRmq([3, 1]).try_best(1..1) == NoneLinearRmq([3, 1]).try_best(0..2) == Some(1)