segtree
The segtree module.
Generated from spec/std/segtree.cp by cpl doc --format json.
SegTree
pub struct SegTree<D, T, F = Int>(m: Monoid<T>)Point update and range fold. The operation is a bare operator (+, *, ^, &, |,
min, max, gcd) or your own Monoid(id, op): SegTree<V, Int>(max, a),
SegTree<V, Int>(+), SegTree<V, Run>(Monoid(Run.empty, Run.join), a).
set and fold are O(log n), and so are right_while and left_while; memory is
2 * bit_ceil(n) values. The fold keeps the order of the positions, so
non-commutative operations work.
SegTree.source
source: ?(D -> T)What each position holds, for a tree built with of.
SegTree.new
fn new<M, A>(op: ?M = None, a: ?[D]T = None, fill: ?T = None, act: A = NoAction(), over: ?Range<Int> = None) -> SegTree<D, T, F>A tree over D folding with op: built from a, filled with fill, or holding the identity
everywhere when neither is given. op is a bare operator (+, *, ^, &, |, min,
max, gcd) or a Monoid(id, op).
act: adds range tags (apply, apply_all); with act: and no op the tree applies tags
and reads points only. When the tag monoid is Commutative the tree skips push-down, which
changes speed, never answers. over: lo..hi covers a huge Int range instead, making nodes
on first touch; positions outside the touched ones hold fill or the identity.
- cost: O(|D|); O(1) with
over: - empty: an empty
Dgives a tree whose every fold is the identity - order: positions keep the domain
Dofa - traps: when both
aandfillare given, orover:is given together witha
Examples:
SegTree(+, [1, 2, 3]).all == 6SegTree<0..4, Int>(max, fill: 5).fold(1..3) == 5SegTree<0..4, Int>(+).all == 0var s = SegTree<Int, Int>(+, over: 0..1_000_000_000); s.set(999_999_999, 4); s.all == 4
SegTree.build
fn build(m: Monoid<T>, a: ?[D]T, fill: ?T) -> SegTree<D, T, F>SegTree.build_lazy
fn build_lazy(m: Monoid<T>, a: ?[D]T, fill: ?T, resolved: Action<T, F>) -> SegTree<D, T, F>SegTree.put
fn put(self, p: Int, f: F)SegTree.push
fn push(self, p: Int)SegTree.open
fn open(self, l: Int, h: Int)SegTree.pull_node
fn pull_node(self, p: Int)SegTree.apply
fn apply(mut self, r: Range<D>, f: F)Apply tag f to every position of r: each fold over r then sees the values with f
applied, through the action given to act:.
- cost: O(log |D|)
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var s = SegTree(+, [1, 2, 3], act: add); s.apply(0..2, 10); s.all == 26var s = SegTree(max, [1, 2, 3], act: add); s.apply(0..1, 5); s.all == 6
SegTree.apply_all
fn apply_all(mut self, f: F)Apply tag f to every position; apply(D.all, f).
- cost: O(1) amortized when the tags commute, else O(|D|)
- empty: changes nothing for an empty
D - traps: never
Examples:
var s = SegTree(+, [1, 2, 3], act: add); s.apply_all(1); s.all == 9
SegTree.fold
fn fold(self, r: Range<D>) -> TThe fold of the values in r, left to right: op(op(a[l], a[l + 1]), ...).
- cost: O(log |D|)
- empty: the identity
- traps: when a non-empty
rreaches outsideD
Examples:
var s = SegTree(+, [1, 2, 3], act: add); s.apply(1..3, 1); s.fold(1..3) == 7
SegTree.right_while
fn right_while(self, from: Cut<D>, ok: T -> Bool) -> Cut<D>The last cut d at or right of from such that ok(fold(from..d)) holds. ok must be
monotone (once false it stays false as d moves right) and true on the identity, so from
itself always qualifies. Replaces max_right.
- cost: O(log |D|)
- ties: the rightmost qualifying cut
- traps: when
ok(identity)is false
Examples:
SegTree(+, [1, 2, 3, 4]).right_while((0..0).r, s => s <= 3) == (0..2).rSegTree(+, [1, 2, 3, 4]).right_while((0..1).r, s => s <= 5) == (0..3).rSegTree(+, [1, 2, 3, 4]).right_while((0..0).r, s => s <= 100) == (0..4).r
SegTree.left_while
fn left_while(self, to: Cut<D>, ok: T -> Bool) -> Cut<D>The first cut d at or left of to such that ok(fold(d..to)) holds. ok must be
monotone (once false it stays false as d moves left) and true on the identity, so to
itself always qualifies. Replaces min_left.
- cost: O(log |D|)
- ties: the leftmost qualifying cut
- traps: when
ok(identity)is false
Examples:
SegTree(+, [1, 2, 3, 4]).left_while((0..4).r, s => s <= 7) == (0..2).rSegTree(+, [1, 2, 3, 4]).left_while((0..4).r, s => s <= 3) == (0..4).r
SegTree.of
fn of<M>(op: M, f: D -> T) -> SegTree<D, T>A tree whose position i holds f(i). f is kept: when something it reads changes,
refresh(i) recomputes position i, so the formula is written once instead of at every
update site.
- cost: O(|D|), calling
fonce per position in key order - empty: an empty
Dgives a tree whose every fold is the identity - order: position
iholdsf(i) - traps: never
Examples:
let w = [1, 2, 3]; SegTree<0..3, Int>.of(+, i => w[i] * 2).all == 12
SegTree.refresh
fn refresh(mut self, i: D)Recompute position i as f(i) with the formula given to of, and update its ancestors.
- cost: O(log |D|) plus one call of
f - traps: when
iis outsideD, or the tree was not built withof
Examples:
var w = [1, 2, 3]; var s = SegTree<0..3, Int>.of(+, i => w[i]); w[1] = 10; s.refresh(1); s.all == 14
SegTree.get
fn get(self, i: D) -> TThe value at position i, with every tag applied.
- cost: O(1); O(log |D|) on a tree with
act: - traps: when
iis outsideD
Examples:
SegTree(+, [4, 5, 6]).get(1) == 5var s = SegTree(act: assign, [1, 2, 3]); s.apply(0..2, Some(9)); s.get(1) == 9
SegTree.set
fn set(mut self, i: D, x: T)Make position i hold x, replacing any tags applied to it, and update its ancestors.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
var s = SegTree(+, [1, 2, 3]); s.set(0, 10); s.all == 15
SegTree.at
fn at(mut self, i: D) -> lends mut TPosition i as a writable place: st.at(i) += x, st.at(i) max= x. The ancestors are
updated when the write ends, so each use is one set; read with get instead.
- cost: O(log |D|) per write
- traps: when
iis outsideD
Examples:
var s = SegTree(+, [1, 2, 3]); s.at(0) += 5; s.all == 11
SegTree.pull
fn pull(mut self, i: D)SegTree.update
fn update(mut self, i: D, f: T -> T)Replace the value v at i with f(v); set(i, f(get(i))) in one walk.
- cost: O(log |D|) plus one call of
f - traps: when
iis outsideD
Examples:
var s = SegTree(+, [1, 2, 3]); s.update(2, x => x * 10); s.all == 33
SegTree.all
fn all(self) -> TThe fold of every position, left to right.
- cost: O(1)
- empty: the identity for an empty
D - traps: never
Examples:
SegTree(max, [3, 9, 4]).all == 9
SegTree.monoid
fn monoid(self) -> Monoid<T>The operation the tree folds with, as its (id, op) pair.
- cost: O(1)
- traps: never
Examples:
SegTree(+, [1]).monoid.id == 0
SegTree.try_fold
fn try_fold(self, r: Range<D>) -> ?TThe fold of r, or None when r is empty; for operations whose identity is only a
sentinel.
- cost: O(log |D|)
- empty:
None - traps: when a non-empty
rreaches outsideD
Examples:
SegTree(+, [1, 2]).try_fold(0..2) == Some(3)SegTree(+, [1, 2]).try_fold(1..1) == None
SegTree.clear
fn clear(mut self, fill: ?T = None)Make every position hold fill, or the identity when fill is None, dropping all pending
tags; the storage is reused. A tree built with of keeps its formula.
- cost: O(|D|)
- empty: nothing to reset for an empty
D - traps: never
Examples:
var s = SegTree(+, [1, 2, 3]); s.clear(); s.all == 0var s = SegTree(+, [1, 2, 3]); s.clear(fill: 2); s.all == 6
SegTree.walk
fn walk(self, r: Range<D>) -> yields TThe values of the canonical nodes that exactly cover r: the maximal aligned blocks of the
tree's bit_ceil(|D|) leaves inside r. Their fold, left to right, is fold(r).
- cost: O(log |D|)
- empty: yields nothing
- order: left to right; at most
2 * log2(bit_ceil(|D|))values - traps: when a non-empty
rreaches outsideD
Examples:
SegTree(+, [1, 2, 3, 4]).walk(0..3).collect() == [3, 3]SegTree(+, [1, 2, 3, 4]).walk(1..4).collect() == [2, 7]
MergeSortTree
pub struct MergeSortTree<D, T>Static merge-sort tree for orthogonal 2D range counting over [D]T.
Build in O(n log n) time and memory; answer value-range counts over any Range<D> in O(log^2 n).
MergeSortTree.new
fn new(a: [D]T) -> MergeSortTree<D, T>A static tree over a whose nodes hold their values sorted, for counting values in a range.
- cost: O(|D| log |D|) time and memory
- empty: an empty
agives a tree where every count is 0 - order: positions keep the domain
Dofa - traps: never
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_lt(0..5, 3) == 2
MergeSortTree.lower_idx
fn lower_idx(self, u: Int, x: T) -> IntMergeSortTree.upper_idx
fn upper_idx(self, u: Int, x: T) -> IntMergeSortTree.count_lt
fn count_lt(self, r: Range<D>, x: T) -> IntThe number of positions in r whose value is < x.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_lt(0..5, 3) == 2
MergeSortTree.count_le
fn count_le(self, r: Range<D>, x: T) -> IntThe number of positions in r whose value is <= x.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_le(0..5, 3) == 3
MergeSortTree.count_in
fn count_in(self, r: Range<D>, lo_v: T, hi_v: T) -> IntThe number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_in(1..4, 1, 4) == 3MergeSortTree([3, 1, 4, 1, 5]).count_in(0..5, 4, 3) == 0
MergeSortTree.count_gt
fn count_gt(self, r: Range<D>, x: T) -> IntThe number of positions in r whose value is > x.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_gt(0..5, 3) == 2
MergeSortTree.count_ge
fn count_ge(self, r: Range<D>, x: T) -> IntThe number of positions in r whose value is >= x.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).count_ge(0..5, 4) == 2
MergeSortTree.first_ge
fn first_ge(self, r: Range<D>, x: T) -> ?TThe smallest value in r that is >= x, or None.
- cost: O(log^2 |D|)
- empty:
None - ties: equal values are interchangeable; the value is returned, not a position
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).first_ge(0..3, 2) == Some(3)MergeSortTree([3, 1, 4, 1, 5]).first_ge(0..3, 5) == None
MergeSortTree.last_le
fn last_le(self, r: Range<D>, x: T) -> ?TThe largest value in r that is <= x, or None.
- cost: O(log^2 |D|)
- empty:
None - ties: equal values are interchangeable; the value is returned, not a position
- traps: when a non-empty
rreaches outsideD
Examples:
MergeSortTree([3, 1, 4, 1, 5]).last_le(2..5, 3) == Some(1)MergeSortTree([3, 1, 4, 1, 5]).last_le(2..5, 0) == None
SegTree2D
pub struct SegTree2D<R, C, T>(m: Monoid<T>)O(|R| * |C|) space. Iterative 2D segment tree: point update and rectangle fold in O(log |R| * log |C|).
SegTree2D.fold_row
fn fold_row(self, i: Int, cl: Int, ch: Int) -> TSegTree2D.new
fn new<M>(op: M, a: ?[R, C]T = None, fill: ?T = None) -> SegTree2D<R, C, T>A grid tree over (R, C) folding with op: built from a, filled with fill, or holding
the identity everywhere. op must be Commutative, since a rectangle is folded in
row-blocks and column-blocks rather than in one order.
- cost: O(|R| * |C|)
- empty: an empty
RorCgives a tree whose every fold is the identity - order: cells keep the domains
RandCofa - traps: when both
aandfillare given
Examples:
SegTree2D<0..3, 0..3, Int>(+, fill: 1).all == 9
SegTree2D.get
fn get(self, r: R, c: C) -> TThe value of cell (r, c).
- cost: O(1)
- traps: when
ris outsideRorcis outsideC
Examples:
var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.set(1, 2, 7); g.get(1, 2) == 7
SegTree2D.set
fn set(mut self, r: R, c: C, x: T)Make cell (r, c) hold x.
- cost: O(log |R| * log |C|)
- traps: when
ris outsideRorcis outsideC
Examples:
var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.set(0, 0, 5); g.all == 13
SegTree2D.update
fn update(mut self, r: R, c: C, f: T -> T)Replace the value v of cell (r, c) with f(v).
- cost: O(log |R| * log |C|) plus one call of
f - traps: when
ris outsideRorcis outsideC
Examples:
var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.update(2, 2, x => x + 1); g.all == 10
SegTree2D.fold
fn fold(self, rows: Range<R>, cols: Range<C>) -> TThe fold of every cell in rows rows and columns cols.
- cost: O(log |R| * log |C|)
- empty: the identity when
rowsorcolsis empty - traps: when a non-empty range reaches outside its domain
Examples:
SegTree2D<0..3, 0..3, Int>(+, fill: 1).fold(0..2, 1..3) == 4SegTree2D<0..3, 0..3, Int>(+, fill: 1).fold(0..2, 1..1) == 0
SegTree2D.all
fn all(self) -> TThe fold of every cell.
- cost: O(1)
- empty: the identity for an empty grid
- traps: never
Examples:
var g = SegTree2D<0..2, 0..2, Int>(max, fill: 0); g.set(1, 0, 8); g.all == 8
WaveletMatrix
pub struct WaveletMatrix<D>O(|D| log V) build and memory. Wavelet matrix over non-negative integer values: O(log V) range k-th smallest, frequency, value-range count, predecessor/successor, and quantile sum.
WaveletMatrix.ones
fn ones(self, l: Int, i: Int) -> IntWaveletMatrix.below
fn below(self, lo0: Int, hi0: Int, x: Int) -> IntWaveletMatrix.new
fn new(a: [D]Int) -> WaveletMatrix<D>A wavelet matrix over the non-negative values of a, with one bit level per bit of the
largest value (V below is that value plus one).
- cost: O(|D| log V) time and memory
- empty: an empty
agives a matrix where every count is 0 - order: positions keep the domain
Dofa - traps: when some value is negative
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 2) == Some(3)
WaveletMatrix.kth
fn kth(self, r: Range<D>, k: Int) -> ?IntThe k-th smallest value in r, counting from 0 and with repeats, or None when
k >= r.len.
- cost: O(log V)
- empty:
None - ties: equal values are counted once each
- traps: when
k < 0, or a non-emptyrreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 0) == Some(1)WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 2) == Some(3)WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 5) == None
WaveletMatrix.rank
fn rank(self, r: Range<D>, x: Int) -> IntThe number of positions in r holding exactly x; 0 for any x outside 0..V.
- cost: O(log V)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).rank(0..5, 1) == 2
WaveletMatrix.count_lt
fn count_lt(self, r: Range<D>, x: Int) -> IntThe number of positions in r whose value is < x.
- cost: O(log V)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).count_lt(0..5, 4) == 3
WaveletMatrix.count_in
fn count_in(self, r: Range<D>, lo_v: Int, hi_v: Int) -> IntThe number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.
- cost: O(log V)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).count_in(0..5, 1, 3) == 3
WaveletMatrix.prev_val
fn prev_val(self, r: Range<D>, x: Int) -> ?IntThe largest value in r that is < x, or None.
- cost: O(log V)
- empty:
None - ties: equal values are interchangeable; the value is returned, not a position
- traps: when a non-empty
rreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).prev_val(0..5, 3) == Some(1)WaveletMatrix([3, 1, 4, 1, 5]).prev_val(0..5, 1) == None
WaveletMatrix.next_val
fn next_val(self, r: Range<D>, x: Int) -> ?IntThe smallest value in r that is > x, or None.
- cost: O(log V)
- empty:
None - ties: equal values are interchangeable; the value is returned, not a position
- traps: when a non-empty
rreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).next_val(0..5, 3) == Some(4)WaveletMatrix([3, 1, 4, 1, 5]).next_val(0..5, 5) == None
WaveletMatrix.quantile_sum
fn quantile_sum(self, r: Range<D>, k: Int) -> IntThe sum of the k smallest values in r, with repeats.
- cost: O(log V)
- empty: 0 (only
k == 0is allowed) - ties: equal values are counted once each
- traps: when
kis outside0..=r.len, or a non-emptyrreaches outsideD
Examples:
WaveletMatrix([3, 1, 4, 1, 5]).quantile_sum(0..5, 3) == 5WaveletMatrix([3, 1, 4, 1, 5]).quantile_sum(1..3, 0) == 0
DynamicOrderTree
pub struct DynamicOrderTree<D, T>O(|D| log^2 |D|) space. Dynamic point-update + 2D range value-count and k-th structure
(Fenwick of order trees) over [D]T.
DynamicOrderTree.bump
fn bump(mut self, i: Int, x: T, put: Bool)DynamicOrderTree.below
fn below(self, end: Int, x: T, le: Bool) -> IntDynamicOrderTree.span_count
fn span_count(self, r: Range<D>, x: T, le: Bool) -> IntDynamicOrderTree.new
fn new(a: [D]T) -> DynamicOrderTree<D, T>A structure over a answering value counts and order statistics on ranges while positions
are reassigned.
- cost: O(|D| log^2 |D|) time and memory
- empty: an empty
agives a tree where every count is 0 - order: positions keep the domain
Dofa - traps: never
Examples:
DynamicOrderTree([3, 1, 4]).count_lt(0..3, 4) == 2
DynamicOrderTree.set
fn set(mut self, i: D, x: T)Make position i hold x.
- cost: O(log^2 |D|)
- traps: when
iis outsideD
Examples:
var t = DynamicOrderTree([3, 1, 4]); t.set(0, 0); t.kth(0..3, 0) == Some(0)
DynamicOrderTree.get
fn get(self, i: D) -> TThe value at position i.
- cost: O(1)
- traps: when
iis outsideD
Examples:
var t = DynamicOrderTree([3, 1, 4]); t.set(2, 9); t.get(2) == 9
DynamicOrderTree.count_lt
fn count_lt(self, r: Range<D>, x: T) -> IntThe number of positions in r whose value is < x.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
DynamicOrderTree([3, 1, 4]).count_lt(1..3, 4) == 1
DynamicOrderTree.count_in
fn count_in(self, r: Range<D>, lo_v: T, hi_v: T) -> IntThe number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.
- cost: O(log^2 |D|)
- empty: 0
- traps: when a non-empty
rreaches outsideD
Examples:
DynamicOrderTree([3, 1, 4]).count_in(0..3, 1, 3) == 2
DynamicOrderTree.kth
fn kth(self, r: Range<D>, k: Int) -> ?TThe k-th smallest value in r, counting from 0 and with repeats, or None when
k >= r.len.
- cost: O(log^2 |D|)
- empty:
None - ties: equal values are counted once each
- traps: when
k < 0, or a non-emptyrreaches outsideD
Examples:
DynamicOrderTree([3, 1, 4]).kth(0..3, 1) == Some(3)DynamicOrderTree([3, 1, 4]).kth(0..3, 3) == None
MergeSeg
pub struct MergeSeg<D>O(q log |D|) space. Mergeable min-ordered set over domain D for lazily pruned
minimum-alive queries (MergeSeg.singleton, merge, first_alive).
MergeSeg.push_raw
fn push_raw(mut self, x: D)MergeSeg.pop_min
fn pop_min(mut self)MergeSeg.singleton
fn singleton(x: D) -> MergeSeg<D>A set of positions of D holding only x, stored as a sparse binary tree over D.
- cost: O(log |D|)
- traps: when
xis outsideD
Examples:
MergeSeg<0..10>.singleton(3).first_alive(x => true) == Some(3)
MergeSeg.merge
fn merge(self, other: MergeSeg<D>) -> MergeSeg<D>The union of self and other. The result reuses the nodes of both, so neither input may be
used afterwards.
- cost: O(log |D|) amortized per node absorbed
- traps: never
Examples:
var m = MergeSeg<0..10>.singleton(7).merge(MergeSeg<0..10>.singleton(3)); m.first_alive(x => true) == Some(3)
MergeSeg.first_alive
fn first_alive(mut self, alive: D -> Bool) -> ?DThe smallest position x in the set with alive(x), or None. Every position found dead on
the way is removed for good, so alive must be monotone over time: a position never comes
back to life.
- cost: O(log |D|) amortized
- ties: the smallest position in key order
- traps: never
Examples:
var m = MergeSeg<0..10>.singleton(3).merge(MergeSeg<0..10>.singleton(7)); m.first_alive(x => x > 5) == Some(7)var m = MergeSeg<0..10>.singleton(3).merge(MergeSeg<0..10>.singleton(7)); m.first_alive(x => x > 5); m.first_alive(x => true) == Some(7)