Skip to Content
ReferenceLibrary

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.

Source

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, op called O(|D| log |D|) times
  • empty: an empty a builds an empty table; every fold on it traps, try_fold is None
  • order: the table keeps the domain D of a
  • traps: never (a non-idempotent or non-associative op gives unspecified folds; check with idempotent)

Examples:

  • SparseTable(min, [3, 1, 4]).fold(0..3) == 1

Source

SparseTable.fold

fn fold(self, r: Range<D>) -> T

The 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_fold when r may be empty
  • traps: when r is empty or reaches outside D

Examples:

  • SparseTable(max, [3, 1, 4]).fold(0..2) == 3
  • SparseTable(min, [3, 1, 4]).fold(1..2) == 1

Source

SparseTable.try_fold

fn try_fold(self, r: Range<D>) -> ?T

The fold of r like fold, or None when r is empty.

  • cost: O(1)
  • empty: None
  • traps: when a non-empty r reaches outside D

Examples:

  • SparseTable(min, [3, 1, 4]).try_fold(1..1) == None
  • SparseTable(min, [3, 1, 4]).try_fold(1..3) == Some(1)

Source

SparseTable.get

fn get(self, i: D) -> T

The original value at position i (level 0 of the table).

  • cost: O(1)
  • traps: when i is outside D

Examples:

  • SparseTable(min, [3, 1, 4]).get(2) == 4

Source

SparseTable.all

fn all(self) -> T

The fold of every position of D; fold(D.all).

  • cost: O(1)
  • empty: traps on an empty domain
  • traps: when D is empty

Examples:

  • SparseTable(gcd, [4, 6, 10]).all == 2

Source

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.

Source

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, op called O(|D| log |D|) times
  • empty: an empty a builds an empty table; every fold on it traps, try_fold is None
  • order: the table keeps the domain D of a; folds run in domain order
  • traps: never (a non-associative op gives unspecified folds)

Examples:

  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).fold(0..3) == 8

Source

DisjointSparseTable.fold

fn fold(self, r: Range<D>) -> T

The 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 op call
  • empty: traps; use try_fold when r may be empty
  • traps: when r is empty or reaches outside D

Examples:

  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).fold(1..3) == 5
  • DisjointSparseTable((a, b) => a, [7, 8, 9]).fold(1..3) == 8

Source

DisjointSparseTable.try_fold

fn try_fold(self, r: Range<D>) -> ?T

The fold of r like fold, or None when r is empty.

  • cost: O(1)
  • empty: None
  • traps: when a non-empty r reaches outside D

Examples:

  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).try_fold(2..2) == None
  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).try_fold(0..2) == Some(4)

Source

DisjointSparseTable.get

fn get(self, i: D) -> T

The original value at position i.

  • cost: O(1)
  • traps: when i is outside D

Examples:

  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).get(0) == 3

Source

DisjointSparseTable.all

fn all(self) -> T

The fold of every position of D, left to right; fold(D.all).

  • cost: O(1)
  • empty: traps on an empty domain
  • traps: when D is empty

Examples:

  • DisjointSparseTable((a, b) => a + b, [3, 1, 4]).all == 8

Source

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, &, |).

Source

SparseTable2D.at

fn at(self, kr: Int, kc: Int, i: Int, j: Int) -> Int

Source

SparseTable2D.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 fold on it traps
  • order: the table keeps the domains R and C of a
  • traps: never (a non-idempotent op gives unspecified folds)

Examples:

  • SparseTable2D(max, [2, 2] (r, c) => r * 2 + c).fold(0..2, 0..2) == 3

Source

SparseTable2D.fold

fn fold(self, rows: Range<R>, cols: Range<C>) -> T

The 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

Source

SparseTable2D.try_fold

fn try_fold(self, rows: Range<R>, cols: Range<C>) -> ?T

The rectangle fold like fold, or None when rows or cols is empty.

  • cost: O(1)
  • empty: None when 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) == None
  • SparseTable2D(min, [2, 2] (r, c) => r * 2 + c).try_fold(0..2, 1..2) == Some(1)

Source

SparseTable2D.get

fn get(self, r: R, c: C) -> T

The original cell value a[r, c].

  • cost: O(1)
  • traps: when r is outside R or c is outside C

Examples:

  • SparseTable2D(min, [2, 2] (r, c) => r * 2 + c).get(1, 0) == 2

Source

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.

Source

LinearRmq.better

fn better(self, i: Int, j: Int) -> Int

Source

LinearRmq.in_block

fn in_block(self, l: Int, r: Int) -> Int

Source

LinearRmq.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 a builds an empty structure; argbest and best on it trap
  • order: the structure keeps the domain D of a
  • traps: never (before must be a strict weak order, or results are unspecified)

Examples:

  • LinearRmq([3, 1, 4]).best(0..3) == 1

Source

LinearRmq.argbest

fn argbest(self, r: Range<D>) -> D

The 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 r is empty or reaches outside D

Examples:

  • LinearRmq([3, 1, 1, 4]).argbest(0..4) == 1
  • LinearRmq([3, 1, 4], before: (x, y) => x > y).argbest(0..3) == 2

Source

LinearRmq.best

fn best(self, r: Range<D>) -> T

The value of the best element of the non-empty range r under before; a[argbest(r)].

  • cost: O(1)
  • empty: traps; use try_best when r may be empty
  • ties: equal-best values are interchangeable; the value at the leftmost is returned
  • traps: when r is empty or reaches outside D

Examples:

  • LinearRmq([3, 1, 4], before: (x, y) => x > y).best(0..3) == 4

Source

LinearRmq.try_best

fn try_best(self, r: Range<D>) -> ?T

The 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 r reaches outside D

Examples:

  • LinearRmq([3, 1]).try_best(1..1) == None
  • LinearRmq([3, 1]).try_best(0..2) == Some(1)

Source

On this page