beats
Segment Tree Beats over a domain D of Int values.
Generated from spec/std/beats.cp by cpl doc --format json.
BeatsSegTree
pub struct BeatsSegTree<D>Segment Tree Beats over a domain D of Int values.
Supports chmin, chmax, add, sum, min_val, max_val, and get.
BeatsSegTree.new
fn new(a: ?[D]Int = None, fill: ?Int = None) -> BeatsSegTree<D>A Segment Tree Beats over D holding the values of a, or fill at every position, or
zero everywhere when neither is given. Every node keeps the exact maximum, second maximum
and its count, the same for the minimum, and the sum.
- cost: O(|D|)
- empty: an empty
Dbuilds a tree whose sums are zero and whose extrema areNone - order: positions keep the domain
D(ofa, when given) - traps: when both
aandfillare given
Examples:
BeatsSegTree([5, 1, 4]).all_sum == 10BeatsSegTree<0..3>(fill: 2).all_sum == 6
BeatsSegTree.pull
fn pull(mut self, u: Int)BeatsSegTree.build
fn build(mut self, u: Int, nl: Int, nr: Int, vals: List<Int>)BeatsSegTree.apply_add
fn apply_add(mut self, u: Int, len: Int, x: Int)BeatsSegTree.apply_chmin
fn apply_chmin(mut self, u: Int, x: Int)BeatsSegTree.apply_chmax
fn apply_chmax(mut self, u: Int, x: Int)BeatsSegTree.push
fn push(mut self, u: Int, nl: Int, nr: Int)BeatsSegTree.chmin_rec
fn chmin_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)BeatsSegTree.chmin
fn chmin(mut self, r: Range<D>, x: Int)Replace every a[i] in r with min(a[i], x). Descends only into nodes whose maximum
exceeds x and whose second maximum does not, where the update is a tag.
- cost: O(log |D|) amortized; O(log^2 |D|) amortized when mixed with
add - empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.chmin(0..3, 3); t.all_sum == 7
BeatsSegTree.chmax_rec
fn chmax_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)BeatsSegTree.chmax
fn chmax(mut self, r: Range<D>, x: Int)Replace every a[i] in r with max(a[i], x); the mirror of chmin.
- cost: O(log |D|) amortized; O(log^2 |D|) amortized when mixed with
add - empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.chmax(0..2, 2); t.all_sum == 11
BeatsSegTree.add_rec
fn add_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)BeatsSegTree.add
fn add(mut self, r: Range<D>, x: Int)Add x to every a[i] in r.
- cost: O(log |D|)
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD(overflow wraps in release, traps in debug)
Examples:
var t = BeatsSegTree([5, 1, 4]); t.add(1..3, 10); t.sum(0..3) == 30
BeatsSegTree.sum_rec
fn sum_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> IntBeatsSegTree.sum
fn sum(mut self, r: Range<D>) -> IntThe sum of the current values in r. Takes mut self because it pushes pending tags.
- cost: O(log |D|)
- empty: zero
- traps: when a non-empty
rreaches outsideD
Examples:
BeatsSegTree([5, 1, 4]).sum(1..3) == 5BeatsSegTree([5, 1, 4]).sum(1..1) == 0
BeatsSegTree.min_rec
fn min_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> IntBeatsSegTree.min_val
fn min_val(mut self, r: Range<D>) -> ?IntThe least current value in r, or None when r is empty.
- cost: O(log |D|)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: when a non-empty
rreaches outsideD
Examples:
BeatsSegTree([5, 1, 4]).min_val(0..3) == Some(1)BeatsSegTree([5, 1, 4]).min_val(2..2) == None
BeatsSegTree.max_rec
fn max_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> IntBeatsSegTree.max_val
fn max_val(mut self, r: Range<D>) -> ?IntThe greatest current value in r, or None when r is empty.
- cost: O(log |D|)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: when a non-empty
rreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.chmin(0..1, 2); t.max_val(0..3) == Some(4)
BeatsSegTree.get
fn get(mut self, i: D) -> IntThe current value at position i.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
BeatsSegTree([5, 1, 4]).get(2) == 4
BeatsSegTree.div_rec
fn div_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, d: Int, rem: Bool)BeatsSegTree.set
fn set(mut self, i: D, x: Int)Assign a[i] = x, replacing whatever earlier updates left there.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.set(1, 9); t.all_max == Some(9)
BeatsSegTree.assign
fn assign(mut self, r: Range<D>, x: Int)Overwrite every position in r with x.
- cost: O(log |D|) amortized
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.assign(0..2, 0); t.all_sum == 4
BeatsSegTree.chdiv
fn chdiv(mut self, r: Range<D>, d: Int)Replace every a[i] in r with a[i] / d, rounding toward negative infinity. A node whose
values all map to the same shift becomes a single add tag, so each value is divided
O(log V) times before it settles, for values of magnitude at most V.
- cost: O(log |D| log V) amortized
- empty: changes nothing
- traps: when
d <= 0, or a non-emptyrreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.chdiv(0..3, 2); t.all_sum == 4var t = BeatsSegTree([-3]); t.chdiv(0..1, 2); t.get(0) == -2
BeatsSegTree.chmod
fn chmod(mut self, r: Range<D>, m: Int)Replace every a[i] in r with a[i] mod m, the remainder in 0..m (floored, so
negative values map into 0..m too). Nodes whose maximum is below m are skipped.
- cost: O(log |D| log V) amortized
- empty: changes nothing
- traps: when
m <= 0, or a non-emptyrreaches outsideD
Examples:
var t = BeatsSegTree([5, 1, 4]); t.chmod(0..3, 3); t.all_sum == 4
BeatsSegTree.all_sum
fn all_sum(self) -> IntThe sum of every current value in D.
- cost: O(1)
- empty: zero on an empty domain
- traps: never
Examples:
BeatsSegTree([5, 1, 4]).all_sum == 10
BeatsSegTree.all_min
fn all_min(self) -> ?IntThe least current value in D, or None when D is empty.
- cost: O(1)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: never
Examples:
BeatsSegTree([5, 1, 4]).all_min == Some(1)
BeatsSegTree.all_max
fn all_max(self) -> ?IntThe greatest current value in D, or None when D is empty.
- cost: O(1)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: never
Examples:
BeatsSegTree([5, 1, 4]).all_max == Some(5)
HistoricBeatsSegTree
pub struct HistoricBeatsSegTree<D>O(|D|) space. Segment Tree Beats with historic maximum and historic sum tracking under
range chmin, chmax, and add (Ji Driver with historic tags).
HistoricBeatsSegTree.new
fn new(a: ?[D]Int = None, fill: ?Int = None) -> HistoricBeatsSegTree<D>A Beats tree that also tracks history, holding a, or fill everywhere, or zeros. Each
position remembers the greatest value it has held and the running sum of its values over
versions; version 0 is the initial array, and every chmin, chmax or add call makes
one new version of the whole array.
- cost: O(|D|)
- empty: an empty
Dbuilds a tree whose sums are zero and whose maxima areNone - order: positions keep the domain
D(ofa, when given) - traps: when both
aandfillare given
Examples:
HistoricBeatsSegTree([1, 2]).hist_sum(0..2) == 3
HistoricBeatsSegTree.build
fn build(mut self, u: Int, nl: Int, nr: Int, vals: List<Int>)HistoricBeatsSegTree.pull
fn pull(mut self, u: Int)HistoricBeatsSegTree.compose
fn compose(mut self, u: Int, k: Int, a: Int, h: Int, cc: Int)HistoricBeatsSegTree.apply
fn apply(mut self, u: Int, len: Int, a1: Int, h1: Int, c1: Int, a2: Int, h2: Int, c2: Int, a3: Int, h3: Int, c3: Int)HistoricBeatsSegTree.give
fn give(mut self, v: Int, len: Int, u: Int, pmax: Int, pmin: Int)HistoricBeatsSegTree.push
fn push(mut self, u: Int, nl: Int, nr: Int)HistoricBeatsSegTree.upd
fn upd(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, op: Int, x: Int)HistoricBeatsSegTree.update
fn update(mut self, r: Range<D>, op: Int, x: Int)HistoricBeatsSegTree.chmin
fn chmin(mut self, r: Range<D>, x: Int)Replace every a[i] in r with min(a[i], x), then record a new version.
- cost: O(log |D|) amortized; O(log^2 |D|) amortized when mixed with
add - empty: changes no value but still records a version
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([5, 1]); t.chmin(0..2, 2); t.sum(0..2) == 3 and t.hist_max(0..1) == Some(5)
HistoricBeatsSegTree.chmax
fn chmax(mut self, r: Range<D>, x: Int)Replace every a[i] in r with max(a[i], x), then record a new version.
- cost: O(log |D|) amortized; O(log^2 |D|) amortized when mixed with
add - empty: changes no value but still records a version
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([5, 1]); t.chmax(0..2, 3); t.sum(0..2) == 8
HistoricBeatsSegTree.add
fn add(mut self, r: Range<D>, x: Int)Add x to every a[i] in r, then record a new version.
- cost: O(log |D|)
- empty: changes no value but still records a version
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.sum(0..2) == 6
HistoricBeatsSegTree.ask
fn ask(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, what: Int) -> IntHistoricBeatsSegTree.query
fn query(mut self, r: Range<D>, what: Int) -> ?IntHistoricBeatsSegTree.sum
fn sum(mut self, r: Range<D>) -> IntThe sum of the current values in r.
- cost: O(log |D|)
- empty: zero
- traps: when a non-empty
rreaches outsideD
Examples:
HistoricBeatsSegTree([1, 2]).sum(0..2) == 3
HistoricBeatsSegTree.max_val
fn max_val(mut self, r: Range<D>) -> ?IntThe greatest current value in r, or None when r is empty.
- cost: O(log |D|)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([1, 2]); t.add(0..2, 5); t.add(0..2, -10); t.max_val(0..1) == Some(-4)
HistoricBeatsSegTree.hist_max
fn hist_max(mut self, r: Range<D>) -> ?IntThe greatest value any position in r has held in any version, the initial one included;
None when r is empty.
- cost: O(log |D|)
- empty:
None - ties: returns a value, so equal candidates are indistinguishable
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([1, 2]); t.add(0..2, 5); t.add(0..2, -10); t.hist_max(0..1) == Some(6)HistoricBeatsSegTree([1, 2]).hist_max(1..1) == None
HistoricBeatsSegTree.hist_sum
fn hist_sum(mut self, r: Range<D>) -> IntThe sum over positions i in r of every value a[i] has had, one term per version:
the initial array plus the array after each update call.
- cost: O(log |D|)
- empty: zero
- traps: when a non-empty
rreaches outsideD
Examples:
var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.hist_sum(0..2) == 9var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.hist_sum(1..2) == 4