Skip to Content
ReferenceLibrary

prefix

O(n) calls of f.

Generated from spec/std/prefix.cp by cpl doc --format json.

FillOrder

pub enum FillOrder = Forward | Reverse

Fill direction for an append-only Prefix.filling(...) table.

Source

FillOrder.Forward

Forward

Source

FillOrder.Reverse

Reverse

Source

FillPrefix

pub struct FillPrefix<D, T>

Append-only 1-D prefix/suffix sum table returned by Prefix<D, T>.filling(...).

Source

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 i is 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

Source

FillPrefix.prefix

fn prefix(self, b: Cut<D>) -> T

The 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 b is not yet written (with Reverse, 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) == 5
  • domain D = 0..3; var f = Prefix<D, Int>.filling(); f.prefix(0) == 0

Source

FillPrefix.fold

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

The 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 r is 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) == 12
  • domain D = 0..3; var f = Prefix<D, Int>.filling(order: FillOrder.Reverse); f.set(2, 4); f.set(1, 6); f.fold(1..) == 10

Source

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.

Source

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

Source

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

Source

Prefix.prefix

fn prefix(self, b: Cut<D>) -> T

The 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) == 3
  • domain D = 0..3; let p = Prefix<D, Int>([D] v => 1 + Int(v)); p.prefix(0) == 0

Source

Prefix.of_cuts

fn of_cuts(p: [D.cuts]T) -> Prefix<D, T>

Source

Prefix.fold

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

The 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

Source

Prefix.cyclic_sum

fn cyclic_sum(self, r: RingRange<D>) -> T

The 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

Source

Prefix.get

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

Recover 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

Source

Prefix.suffix

fn suffix(self, b: Cut<D>) -> T

The 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

Source

Prefix.all

fn all(self) -> T

The 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

Source

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, else None
  • 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

Source

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, else None
  • 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

Source

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.

Source

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

Source

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]

Source

Diff.finish

fn finish(self) -> [D]T

The 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

Source

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.

Source

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

Source

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 r is 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

Source

SweepAdd.advance

fn advance(mut self, i: D) -> T

Advance 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 i is 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

Source

SweepAdd.current

fn current(self) -> T

The 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

Source

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.

Source

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

Source

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]

Source

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]

Source

ArithDiff.finish

fn finish(self) -> [D]T

The 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]

Source

On this page