fenwick
Point add and range sum over anything with + and - (Int, Mod<P>).
Generated from spec/std/fenwick.cp by cpl doc --format json.
Fenwick
pub struct Fenwick<D, T>Point add and range sum over anything with + and - (Int, Mod<P>).
Fenwick<D, Int>() starts at zero and Fenwick<D, Int>(a) from an array, in O(n).
add, prefix and sum are O(log n); memory is n + 1 values.
A range is one prefix minus another, so there is no "Fenwick on max": that is a SegTree.
Fenwick.new
fn new(a: ?[D]T = None) -> Fenwick<D, T>A Fenwick tree over D: all zeros, or holding the values of a when given. The values
must form a group under + and - (Int, Mod<P>, F64), since a range sum is one
prefix minus another.
- cost: O(|D|) time; memory |D| + 1 values
- empty: an empty
Dgives a tree whose every sum is zero - order: positions keep the domain
D(ofa, when given) - traps: never
Examples:
Fenwick([1, 2, 3]).all == 6Fenwick<0..3, Int>().all == 0
Fenwick.add
fn add(mut self, i: D, x: T)Add x to the value at position i: a[i] += x.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
var f = Fenwick([1, 2, 3]); f.add(0, 5); f.fold(0..2) == 8
Fenwick.prefix
fn prefix(self, b: Cut<D>) -> TThe sum of every position left of the boundary b. For a position v, prefix(v.r)
includes v and prefix(v.l) does not; the start cut gives zero.
- cost: O(log |D|)
- traps: never (
bis a cut ofDby type)
Examples:
Fenwick([1, 2, 3]).prefix((0..2).r) == 3Fenwick([1, 2, 3]).prefix((0..0).r) == 0
Fenwick.fold
fn fold(self, r: Range<D>) -> TThe sum over the positions of r: prefix(r.r) - prefix(r.l). Accepts every range form
(l..r, l..=r, ..i, i..).
- cost: O(log |D|)
- empty: zero
- traps: when a non-empty
rreaches outsideD
Examples:
Fenwick([1, 2, 3]).fold(1..3) == 5Fenwick([1, 2, 3]).fold(2..2) == 0
Fenwick.first_ge
fn first_ge(self, target: Int) -> ?Cut<D>The smallest boundary b with prefix(b) >= target, by binary lifting over the tree;
None when even the whole sum is below target. A target <= 0 gives the start cut.
Correct only when every value is non-negative (prefix sums non-decreasing).
- cost: O(log |D|)
- ties: the leftmost qualifying cut
- traps: never (negative values give an unspecified cut, not a trap)
Examples:
Fenwick([1, 2, 3]).first_ge(3) == Some((0..2).r)Fenwick([1, 2, 3]).first_ge(7) == NoneFenwick([1, 2, 3]).first_ge(0) == Some((0..0).r)
Fenwick.kth
fn kth(self, k: Int) -> ?DThe k-th item counting from 1, when position d holds a[d] items: the first d with
prefix(d.r) >= k, or None when fewer than k items exist in total. Positions with value
zero are never returned. For non-negative values.
- cost: O(log |D|)
- ties: the leftmost qualifying position
- traps: when
k < 1(negative values give an unspecified position, not a trap)
Examples:
Fenwick([1, 0, 2]).kth(2) == Some(2)Fenwick([1, 0, 2]).kth(1) == Some(0)Fenwick([1, 0, 2]).kth(4) == None
Fenwick.get
fn get(self, i: D) -> TThe current value at position i: sum(i..=i).
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
Fenwick([1, 2, 3]).get(1) == 2
Fenwick.set
fn set(mut self, i: D, x: T)Assign a[i] = x, by adding the difference x - get(i); also the write-through place for
f[i] = x.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
var f = Fenwick([1, 2, 3]); f.set(1, 5); f.all == 9
Fenwick.all
fn all(self) -> TThe sum of every position of D, kept current by add, set and clear.
- cost: O(1)
- empty: zero on an empty domain
- traps: never
Examples:
Fenwick([1, 2, 3]).all == 6
Fenwick.suffix
fn suffix(self, b: Cut<D>) -> TThe sum of every position right of the boundary b: all - prefix(b). The end cut gives zero.
- cost: O(log |D|)
- traps: never
Examples:
Fenwick([1, 2, 3]).suffix((0..1).r) == 5Fenwick([1, 2, 3]).suffix((0..3).r) == 0
Fenwick.first_gt
fn first_gt(self, target: Int) -> ?Cut<D>The smallest boundary b with prefix(b) > target, or None when the whole sum is at most
target. For non-negative values.
- cost: O(log |D|)
- ties: the leftmost qualifying cut
- traps: never (negative values give an unspecified cut, not a trap)
Examples:
Fenwick([1, 2, 3]).first_gt(3) == Some((0..3).r)Fenwick([1, 2, 3]).first_gt(6) == None
Fenwick.clear
fn clear(mut self)Reset every value to zero, keeping the domain and the allocation.
- cost: O(|D|)
- traps: never
Examples:
var f = Fenwick([1, 2, 3]); f.clear(); f.all == 0
Fenwick2D
pub struct Fenwick2D<R, C, T>Point add and rectangle sum on a grid. add and sum are O(log R * log C);
memory is (R + 1) * (C + 1) values.
Fenwick2D.new
fn new() -> Fenwick2D<R, C, T>An all-zero 2-D Fenwick tree over the grid R by C.
- cost: O(|R| |C|) time; memory (|R| + 1)(|C| + 1) values
- traps: never
Examples:
Fenwick2D<0..2, 0..2, Int>().fold(0..2, 0..2) == 0
Fenwick2D.add
fn add(mut self, r: R, c: C, x: T)Add x to the cell (r, c): a[r, c] += x.
- cost: O(log |R| log |C|)
- traps: when
ris outsideRorcis outsideC
Examples:
var f = Fenwick2D<0..2, 0..2, Int>(); f.add(1, 0, 5); f.fold(1..2, 0..1) == 5
Fenwick2D.corner
fn corner(self, r: Int, c: Int) -> TFenwick2D.fold
fn fold(self, rows: Range<R>, cols: Range<C>) -> TThe sum over the rectangle rows by cols, by inclusion-exclusion over four prefixes.
- cost: O(log |R| log |C|)
- empty: zero when either range is empty
- traps: when a range of a non-empty rectangle reaches outside its domain
Examples:
var f = Fenwick2D<0..2, 0..2, Int>(); f.add(0, 0, 1); f.add(1, 1, 2); f.fold(0..2, 1..2) == 2var f = Fenwick2D<0..2, 0..2, Int>(); f.add(0, 0, 1); f.fold(0..2, 1..1) == 0
Fenwick2D.prefix
fn prefix(self, r: Cut<R>, c: Cut<C>) -> TThe sum of every cell above the row cut r and left of the column cut c.
- cost: O(log |R| log |C|)
- traps: never
Examples:
var f = Fenwick2D<0..2, 0..2, Int>(); f.add(0, 0, 1); f.add(1, 1, 2); f.prefix((0..1).r, (0..2).r) == 1
Fenwick2D.get
fn get(self, r: R, c: C) -> TThe current value of the cell (r, c).
- cost: O(log |R| log |C|)
- traps: when
ris outsideRorcis outsideC
Examples:
var f = Fenwick2D<0..2, 0..2, Int>(); f.add(1, 1, 2); f.get(1, 1) == 2
Fenwick2D.clear
fn clear(mut self)Reset every cell to zero, keeping the domains and the allocation.
- cost: O(|R| |C|)
- traps: never
Examples:
var f = Fenwick2D<0..2, 0..2, Int>(); f.add(1, 1, 2); f.clear(); f.get(1, 1) == 0
DualFenwick
pub struct DualFenwick<D, T>Range add and point get via a difference Fenwick tree.
DualFenwick<D, Int>() starts at zero and DualFenwick<D, Int>(a) from an array, in O(n).
add and get are O(log n); memory is n + 1 values.
DualFenwick.new
fn new(a: ?[D]T = None) -> DualFenwick<D, T>A range-add, point-get Fenwick tree over D: all zeros, or holding the values of a when
given. It stores differences, so get(i) is a prefix sum of them.
- cost: O(|D|) time; memory |D| + 1 values
- empty: an empty
Dgives a tree with no positions to read - order: positions keep the domain
D(ofa, when given) - traps: never
Examples:
DualFenwick([1, 2, 3]).get(2) == 3
DualFenwick.add_at
fn add_at(mut self, p0: Int, x: T)DualFenwick.add
fn add(mut self, r: Range<D>, x: T)Add x to every position of r.
- cost: O(log |D|)
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var d = DualFenwick([1, 2, 3]); d.add(0..2, 10); d.get(1) == 12var d = DualFenwick([1, 2, 3]); d.add(0..2, 10); d.get(2) == 3
DualFenwick.get
fn get(self, i: D) -> TThe current value at position i: its initial value plus every x added over a range
containing i.
- cost: O(log |D|)
- traps: when
iis outsideD
Examples:
var d = DualFenwick([1, 2, 3]); d.add(1..3, 5); d.get(1) == 7
DualFenwick.clear
fn clear(mut self)Reset every value to zero, keeping the domain and the allocation.
- cost: O(|D|)
- traps: never
Examples:
var d = DualFenwick([1, 2, 3]); d.clear(); d.get(0) == 0
SparseFenwick2D
pub struct SparseFenwick2D<T>SparseFenwick2D.new
fn new() -> SparseFenwick2D<T>An empty offline 2-D Fenwick builder. Use it in two phases: register every point that will
ever be updated with add_point, call build once, then use add and sum.
- cost: O(1)
- traps: never
Examples:
var f = SparseFenwick2D<Int>(); f.build(); f.fold(0..10, 0..10) == 0
SparseFenwick2D.add_point
fn add_point(mut self, x: Int, y: Int)Register the point (x, y) as a future add target. Registering a point twice is harmless.
- cost: O(1) amortized
- traps: after
build
Examples:
var f = SparseFenwick2D<Int>(); f.add_point(5, 7); f.add_point(5, 7); f.build(); f.add(5, 7, 3); f.fold(0..10, 0..10) == 3
SparseFenwick2D.build
fn build(mut self)Compress the registered x coordinates, and per x bucket the y coordinates it can
receive, and allocate the bucket trees at zero. Ends the registration phase.
- cost: O(n log n) for
nregistered points; memory O(n log n) - traps: when called a second time
Examples:
var f = SparseFenwick2D<Int>(); f.add_point(1, 2); f.build(); f.fold(1..2, 2..3) == 0
SparseFenwick2D.add
fn add(mut self, x: Int, y: Int, v: T)Add v at the registered point (x, y).
- cost: O(log^2 n)
- traps: before
build, or when(x, y)was never registered
Examples:
var f = SparseFenwick2D<Int>(); f.add_point(1, 2); f.add_point(3, 4); f.build(); f.add(1, 2, 5); f.add(3, 4, 7); f.fold(0..2, 0..10) == 5
SparseFenwick2D.corner
fn corner(self, x: Int, y: Int) -> TSparseFenwick2D.fold
fn fold(self, xs: Range<Int>, ys: Range<Int>) -> TThe total added at registered points with x in xs and y in ys. The ranges are over
raw coordinates; points outside them, or never registered, contribute nothing.
- cost: O(log^2 n)
- empty: zero when either range is empty
- traps: before
build
Examples:
var f = SparseFenwick2D<Int>(); f.add_point(1, 2); f.add_point(3, 4); f.build(); f.add(1, 2, 5); f.add(3, 4, 7); f.fold(0..10, 3..5) == 7var f = SparseFenwick2D<Int>(); f.add_point(1, 2); f.build(); f.add(1, 2, 5); f.fold(2..2, 0..10) == 0