prefix
O(n) calls of f.
Generated from spec/std/prefix.cp by cpl doc --format json.
FillOrder
pub enum FillOrder = Forward | ReverseFill direction for an append-only Prefix.filling(...) table.
FillOrder.Forward
ForwardFillOrder.Reverse
ReverseFillPrefix
pub struct FillPrefix<D, T>Append-only 1-D prefix/suffix sum table returned by Prefix<D, T>.filling(...).
FillPrefix.set
fn set(mut self, i: D, x: T)Write the next cell in fill order (D.first..=D.last for Forward, reverse for Reverse).
Each position is written exactly once, in fill order; the table tracks the next position it expects.
every position is written)
- cost: O(1)
- traps: when
iis not the next position in fill order (out of order, repeated, or after
Examples:
domain D = 0..3; var f = Prefix<D, Int>.filling(); f.set(0, 5); f.set(1, 7); f.prefix(2) == 12
FillPrefix.prefix
fn prefix(self, b: Cut<D>) -> TThe sum of everything left of boundary b; zero at the first cut.
of b is written last)
- cost: O(1)
- traps: when a position left of
bis not yet written (withReverse, every position left
Examples:
domain D = 0..3; var f = Prefix<D, Int>.filling(); f.set(0, 5); f.set(1, 7); f.prefix(1) == 5domain D = 0..3; var f = Prefix<D, Int>.filling(); f.prefix(0) == 0
FillPrefix.fold
fn fold(self, r: Range<D>) -> TThe sum of a[i] for i in r, or 0 when r is empty.
- cost: O(1)
- empty: zero, whatever has been written
- traps: when
ris non-empty and contains a position not yet written
Examples:
domain D = 0..3; var f = Prefix<D, Int>.filling(); f.set(0, 5); f.set(1, 7); f.fold(0..2) == 12domain D = 0..3; var f = Prefix<D, Int>.filling(order: FillOrder.Reverse); f.set(2, 4); f.set(1, 6); f.fold(1..) == 10
Prefix
pub struct Prefix<D, T>Prefix sums over a domain D, a 2-D grid (R, C), or a List<T>, of Ints,
F64s, Mods, or anything else with +, - and a zero.
Construct statically with prefix(a) in O(|D|) / O(|R| * |C|) / O(a.len), or incrementally
with Prefix<...>.filling(order: FillOrder.Forward | FillOrder.Reverse) and O(1) .set(...)
in fill order; .fold(...) and .prefix(...) are O(1) over the already-filled prefix or suffix.
Prefix.new
fn new(a: [D]T) -> Prefix<D, T>Build 1-D prefix sums over a: [D]T; prefix(a) calls it.
- cost: O(|D|) time and space
- empty: a table whose every query is zero
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.all == 6
Prefix.filling
fn filling(order: FillOrder = FillOrder.Forward) -> FillPrefix<D, T>Create an append-only 1-D prefix/suffix sum table filled via .set(i, x) in order.
Forward writes D.first to D.last and answers queries over the written prefix;
Reverse writes D.last to D.first and answers queries over the written suffix.
- cost: O(|D|) time and space
- traps: never
Examples:
domain D = 0..3; var f = Prefix<D, Int>.filling(); f.set(0, 2); f.fold(0..1) == 2
Prefix.prefix
fn prefix(self, b: Cut<D>) -> TThe sum of everything left of boundary b: zero at the first cut, all at the last.
- cost: O(1)
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.prefix(2) == 3domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.prefix(0) == 0
Prefix.of_cuts
fn of_cuts(p: [D.cuts]T) -> Prefix<D, T>Prefix.fold
fn fold(self, r: Range<D>) -> TThe sum of a[i] for i in r, or 0 when r is empty: prefix(r.r) - prefix(r.l).
- cost: O(1)
- empty: zero
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.fold(1..=2) == 5
Prefix.cyclic_sum
fn cyclic_sum(self, r: RingRange<D>) -> TThe sum over a wrapping run of positions, e.g. a.ring.span(i, k): the part from r.start
to D.last plus the part from D.first to r.end when it wraps.
- cost: O(1)
- empty: zero for an empty span
- traps: never
Examples:
domain D = 0..3; let a: [D]Int = [D] v => 1 + Int(v); Prefix<D, Int>(a).cyclic_sum(a.ring.span(2, 2)) == 4
Prefix.get
fn get(self, i: D) -> TRecover the original element a[i], as prefix(i.r) - prefix(i.l).
- cost: O(1)
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.get(1) == 2
Prefix.suffix
fn suffix(self, b: Cut<D>) -> TThe sum of everything right of boundary b: all - prefix(b), zero at the last cut.
- cost: O(1)
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.suffix(1) == 5
Prefix.all
fn all(self) -> TThe sum of the entire domain: prefix at the last cut, zero for an empty domain.
- cost: O(1)
- empty: zero
- traps: never
Examples:
domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.all == 6
Prefix.first_ge
fn first_ge(self, target: T) -> ?Cut<D>The first boundary b with prefix(b) >= target, or None when even all is smaller.
A binary search over the cuts, which needs prefix non-decreasing, so every element must be
non-negative; the table records at build time whether that holds. A target at or below
zero gives the first cut.
- cost: O(log |D|)
- empty: the first cut when
target <= 0, elseNone - ties: the first in cut order (zero elements make equal prefixes)
- traps: when some element is negative
Examples:
Int([2, 0, 3].scan(+).first_ge(2)!) == 1[2, 0, 3].scan(+).first_ge(6) == None
Prefix.first_gt
fn first_gt(self, target: T) -> ?Cut<D>The first boundary b with prefix(b) > target, or None when all <= target.
The same search as first_ge, with the same non-negative requirement.
- cost: O(log |D|)
- empty: the first cut when
target < 0, elseNone - ties: the first in cut order
- traps: when some element is negative
Examples:
Int([2, 0, 3].scan(+).first_gt(2)!) == 3[2, 0, 3].scan(+).first_gt(5) == None
Diff
pub struct Diff<D, T>Offline difference array: Diff<D, T>() for 1-D ranges or Diff<R, C, T>() for 2-D grids.
O(1) range/rectangle add, O(|D|) or O(|R| * |C|) finish.
Diff.new
fn new() -> Diff<D, T>Create an all-zero 1-D difference array over D.
- cost: O(|D|) time and space
- traps: never
Examples:
domain D = 0..3; Diff<D, Int>().finish()[D(1)] == 0
Diff.add
fn add(mut self, r: Range<D>, x: T)Add x to every position in r; an empty r changes nothing.
- cost: O(1)
- empty: no effect
- traps: never
Examples:
domain D = 0..4; var d = Diff<D, Int>(); d.add(1..3, 5); d.add(2..=3, 1); [d.finish()[v] for v in D] == [0, 5, 6, 1]
Diff.finish
fn finish(self) -> [D]TThe accumulated values across D: each position's total of the adds covering it. The
structure is unchanged and can take more adds.
- cost: O(|D|) time and space
- empty: an empty array
- order: keyed by
D - traps: never
Examples:
domain D = 0..3; var d = Diff<D, Int>(); d.add(0..=1, 2); d.finish()[D(1)] == 2 and d.finish()[D(2)] == 0
SweepAdd
pub struct SweepAdd<D, T>O(|D|) space. Online sweep-line difference accumulator: schedule future range adds in O(1)
and advance a cursor through D in order in O(1) per position.
SweepAdd.new
fn new(order: FillOrder = FillOrder.Forward) -> SweepAdd<D, T>Create an all-zero online sweep accumulator in order (Forward or Reverse), with no
position advanced yet.
- cost: O(|D|) time and space
- traps: never
Examples:
domain D = 0..3; var s = SweepAdd<D, Int>(); s.advance(0) == 0
SweepAdd.add
fn add(mut self, r: Range<D>, x: T)Schedule +x across r, which must start at or ahead of the current sweep cursor: no
position of r may have been advanced past already. An empty r changes nothing.
- cost: O(1)
- empty: no effect
- traps: when
ris non-empty and holds a position already advanced to
Examples:
domain D = 0..4; var s = SweepAdd<D, Int>(); s.add(1..=2, 5); let a = s.advance(0); let b = s.advance(1); a == 0 and b == 5
SweepAdd.advance
fn advance(mut self, i: D) -> TAdvance the cursor to i, the next position in fill order, and return the accumulated
value there: the total of every scheduled add covering i.
- cost: O(1)
- traps: when
iis not the next position in fill order
Examples:
domain D = 0..3; var s = SweepAdd<D, Int>(order: FillOrder.Reverse); s.add(1..=2, 4); let a = s.advance(2); s.add(0..=1, 1); let b = s.advance(1); a == 4 and b == 5
SweepAdd.current
fn current(self) -> TThe accumulated value at the most recently advanced position, as advance returned it.
- cost: O(1)
- traps: when no position has been advanced yet
Examples:
domain D = 0..3; var s = SweepAdd<D, Int>(); s.add(0..=0, 7); s.advance(0); s.current == 7
ArithDiff
pub struct ArithDiff<D, T>O(|D|) space. Second-order offline difference array for arithmetic-progression range adds:
O(1) add_arith, O(|D|) finish.
ArithDiff.new
fn new() -> ArithDiff<D, T>Create an all-zero second-order difference array over D.
- cost: O(|D|) time and space
- traps: never
Examples:
domain D = 0..3; ArithDiff<D, Int>().finish()[D(2)] == 0
ArithDiff.add_arith
fn add_arith(mut self, r: Range<D>, start: T, step: T)Add start + step * (i.ord - r.start.ord) to every position i in r: start at the
first position of r, growing by step per position. An empty r changes nothing.
- cost: O(1)
- empty: no effect
- traps: never
Examples:
domain D = 0..5; var d = ArithDiff<D, Int>(); d.add_arith(1..=3, 10, 2); [d.finish()[v] for v in D] == [0, 10, 12, 14, 0]
ArithDiff.add
fn add(mut self, r: Range<D>, x: T)Add a constant x to every position in r: add_arith(r, x, 0).
- cost: O(1)
- empty: no effect
- traps: never
Examples:
domain D = 0..5; var d = ArithDiff<D, Int>(); d.add_arith(1..=3, 10, 2); d.add(0..2, 1); [d.finish()[v] for v in D] == [1, 11, 12, 14, 0]
ArithDiff.finish
fn finish(self) -> [D]TThe accumulated values across D. The structure is unchanged and can take more adds.
- cost: O(|D|) time and space
- empty: an empty array
- order: keyed by
D - traps: never
Examples:
domain D = 0..3; var d = ArithDiff<D, Int>(); d.add_arith(0..=2, 1, 1); [d.finish()[v] for v in D] == [1, 2, 3]