Skip to Content
ReferenceLibrary

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.

Source

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 D gives a tree whose every sum is zero
  • order: positions keep the domain D (of a, when given)
  • traps: never

Examples:

  • Fenwick([1, 2, 3]).all == 6
  • Fenwick<0..3, Int>().all == 0

Source

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

Examples:

  • var f = Fenwick([1, 2, 3]); f.add(0, 5); f.fold(0..2) == 8

Source

Fenwick.prefix

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

The 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 (b is a cut of D by type)

Examples:

  • Fenwick([1, 2, 3]).prefix((0..2).r) == 3
  • Fenwick([1, 2, 3]).prefix((0..0).r) == 0

Source

Fenwick.fold

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

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

Examples:

  • Fenwick([1, 2, 3]).fold(1..3) == 5
  • Fenwick([1, 2, 3]).fold(2..2) == 0

Source

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) == None
  • Fenwick([1, 2, 3]).first_ge(0) == Some((0..0).r)

Source

Fenwick.kth

fn kth(self, k: Int) -> ?D

The 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

Source

Fenwick.get

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

The current value at position i: sum(i..=i).

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

Examples:

  • Fenwick([1, 2, 3]).get(1) == 2

Source

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

Examples:

  • var f = Fenwick([1, 2, 3]); f.set(1, 5); f.all == 9

Source

Fenwick.all

fn all(self) -> T

The 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

Source

Fenwick.suffix

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

The 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) == 5
  • Fenwick([1, 2, 3]).suffix((0..3).r) == 0

Source

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

Source

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

Source

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.

Source

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

Source

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 r is outside R or c is outside C

Examples:

  • var f = Fenwick2D<0..2, 0..2, Int>(); f.add(1, 0, 5); f.fold(1..2, 0..1) == 5

Source

Fenwick2D.corner

fn corner(self, r: Int, c: Int) -> T

Source

Fenwick2D.fold

fn fold(self, rows: Range<R>, cols: Range<C>) -> T

The 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) == 2
  • var f = Fenwick2D<0..2, 0..2, Int>(); f.add(0, 0, 1); f.fold(0..2, 1..1) == 0

Source

Fenwick2D.prefix

fn prefix(self, r: Cut<R>, c: Cut<C>) -> T

The 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

Source

Fenwick2D.get

fn get(self, r: R, c: C) -> T

The current value of the cell (r, c).

  • cost: O(log |R| log |C|)
  • traps: when r is outside R or c is outside C

Examples:

  • var f = Fenwick2D<0..2, 0..2, Int>(); f.add(1, 1, 2); f.get(1, 1) == 2

Source

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

Source

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.

Source

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 D gives a tree with no positions to read
  • order: positions keep the domain D (of a, when given)
  • traps: never

Examples:

  • DualFenwick([1, 2, 3]).get(2) == 3

Source

DualFenwick.add_at

fn add_at(mut self, p0: Int, x: T)

Source

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

Examples:

  • var d = DualFenwick([1, 2, 3]); d.add(0..2, 10); d.get(1) == 12
  • var d = DualFenwick([1, 2, 3]); d.add(0..2, 10); d.get(2) == 3

Source

DualFenwick.get

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

The current value at position i: its initial value plus every x added over a range containing i.

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

Examples:

  • var d = DualFenwick([1, 2, 3]); d.add(1..3, 5); d.get(1) == 7

Source

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

Source

SparseFenwick2D

pub struct SparseFenwick2D<T>

Source

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

Source

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

Source

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 n registered 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

Source

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

Source

SparseFenwick2D.corner

fn corner(self, x: Int, y: Int) -> T

Source

SparseFenwick2D.fold

fn fold(self, xs: Range<Int>, ys: Range<Int>) -> T

The 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) == 7
  • var f = SparseFenwick2D<Int>(); f.add_point(1, 2); f.build(); f.add(1, 2, 5); f.fold(2..2, 0..10) == 0

Source

On this page