Skip to Content
ReferenceLibrary

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.

Source

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 D builds a tree whose sums are zero and whose extrema are None
  • order: positions keep the domain D (of a, when given)
  • traps: when both a and fill are given

Examples:

  • BeatsSegTree([5, 1, 4]).all_sum == 10
  • BeatsSegTree<0..3>(fill: 2).all_sum == 6

Source

BeatsSegTree.pull

fn pull(mut self, u: Int)

Source

BeatsSegTree.build

fn build(mut self, u: Int, nl: Int, nr: Int, vals: List<Int>)

Source

BeatsSegTree.apply_add

fn apply_add(mut self, u: Int, len: Int, x: Int)

Source

BeatsSegTree.apply_chmin

fn apply_chmin(mut self, u: Int, x: Int)

Source

BeatsSegTree.apply_chmax

fn apply_chmax(mut self, u: Int, x: Int)

Source

BeatsSegTree.push

fn push(mut self, u: Int, nl: Int, nr: Int)

Source

BeatsSegTree.chmin_rec

fn chmin_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.chmin(0..3, 3); t.all_sum == 7

Source

BeatsSegTree.chmax_rec

fn chmax_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.chmax(0..2, 2); t.all_sum == 11

Source

BeatsSegTree.add_rec

fn add_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, x: Int)

Source

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 r reaches outside D (overflow wraps in release, traps in debug)

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.add(1..3, 10); t.sum(0..3) == 30

Source

BeatsSegTree.sum_rec

fn sum_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> Int

Source

BeatsSegTree.sum

fn sum(mut self, r: Range<D>) -> Int

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

Examples:

  • BeatsSegTree([5, 1, 4]).sum(1..3) == 5
  • BeatsSegTree([5, 1, 4]).sum(1..1) == 0

Source

BeatsSegTree.min_rec

fn min_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> Int

Source

BeatsSegTree.min_val

fn min_val(mut self, r: Range<D>) -> ?Int

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

Examples:

  • BeatsSegTree([5, 1, 4]).min_val(0..3) == Some(1)
  • BeatsSegTree([5, 1, 4]).min_val(2..2) == None

Source

BeatsSegTree.max_rec

fn max_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int) -> Int

Source

BeatsSegTree.max_val

fn max_val(mut self, r: Range<D>) -> ?Int

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.chmin(0..1, 2); t.max_val(0..3) == Some(4)

Source

BeatsSegTree.get

fn get(mut self, i: D) -> Int

The current value at position i.

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

Examples:

  • BeatsSegTree([5, 1, 4]).get(2) == 4

Source

BeatsSegTree.div_rec

fn div_rec(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, d: Int, rem: Bool)

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.set(1, 9); t.all_max == Some(9)

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.assign(0..2, 0); t.all_sum == 4

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.chdiv(0..3, 2); t.all_sum == 4
  • var t = BeatsSegTree([-3]); t.chdiv(0..1, 2); t.get(0) == -2

Source

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

Examples:

  • var t = BeatsSegTree([5, 1, 4]); t.chmod(0..3, 3); t.all_sum == 4

Source

BeatsSegTree.all_sum

fn all_sum(self) -> Int

The 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

Source

BeatsSegTree.all_min

fn all_min(self) -> ?Int

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

Source

BeatsSegTree.all_max

fn all_max(self) -> ?Int

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

Source

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

Source

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 D builds a tree whose sums are zero and whose maxima are None
  • order: positions keep the domain D (of a, when given)
  • traps: when both a and fill are given

Examples:

  • HistoricBeatsSegTree([1, 2]).hist_sum(0..2) == 3

Source

HistoricBeatsSegTree.build

fn build(mut self, u: Int, nl: Int, nr: Int, vals: List<Int>)

Source

HistoricBeatsSegTree.pull

fn pull(mut self, u: Int)

Source

HistoricBeatsSegTree.compose

fn compose(mut self, u: Int, k: Int, a: Int, h: Int, cc: Int)

Source

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)

Source

HistoricBeatsSegTree.give

fn give(mut self, v: Int, len: Int, u: Int, pmax: Int, pmin: Int)

Source

HistoricBeatsSegTree.push

fn push(mut self, u: Int, nl: Int, nr: Int)

Source

HistoricBeatsSegTree.upd

fn upd(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, op: Int, x: Int)

Source

HistoricBeatsSegTree.update

fn update(mut self, r: Range<D>, op: Int, x: Int)

Source

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

Examples:

  • var t = HistoricBeatsSegTree([5, 1]); t.chmin(0..2, 2); t.sum(0..2) == 3 and t.hist_max(0..1) == Some(5)

Source

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

Examples:

  • var t = HistoricBeatsSegTree([5, 1]); t.chmax(0..2, 3); t.sum(0..2) == 8

Source

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

Examples:

  • var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.sum(0..2) == 6

Source

HistoricBeatsSegTree.ask

fn ask(mut self, u: Int, nl: Int, nr: Int, ql: Int, qr: Int, what: Int) -> Int

Source

HistoricBeatsSegTree.query

fn query(mut self, r: Range<D>, what: Int) -> ?Int

Source

HistoricBeatsSegTree.sum

fn sum(mut self, r: Range<D>) -> Int

The sum of the current values in r.

  • cost: O(log |D|)
  • empty: zero
  • traps: when a non-empty r reaches outside D

Examples:

  • HistoricBeatsSegTree([1, 2]).sum(0..2) == 3

Source

HistoricBeatsSegTree.max_val

fn max_val(mut self, r: Range<D>) -> ?Int

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

Examples:

  • var t = HistoricBeatsSegTree([1, 2]); t.add(0..2, 5); t.add(0..2, -10); t.max_val(0..1) == Some(-4)

Source

HistoricBeatsSegTree.hist_max

fn hist_max(mut self, r: Range<D>) -> ?Int

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

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

Source

HistoricBeatsSegTree.hist_sum

fn hist_sum(mut self, r: Range<D>) -> Int

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

Examples:

  • var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.hist_sum(0..2) == 9
  • var t = HistoricBeatsSegTree([1, 2]); t.add(0..1, 3); t.hist_sum(1..2) == 4

Source

On this page