# Crate fenny

Expand description

## Fenny

Fenny is a library for Fenwick Trees, also known as Binary Indexed Trees (BIT). They are a data structure that support three operations in O(log n) time. The first two correspond to

``````a[i] += v;
a[..=i].iter().sum();``````

The functions for doing these are respectively `update`, `psum`. There is also `first_larger`, which does a binary search to find the first index for which the prefix sum is larger than a some provided value. Being a binary search, it only works if all `a[i]>=0`.

``````// An array of zeros is a Fenwick tree of zeros.
let mut tree = [0; 13];
let root = fenny::get_root_p1(13);
fenny::update(&mut tree, 2, 7);
fenny::update(&mut tree, 5, 20);
assert_eq!(fenny::psum(&tree, 2), 7);
assert_eq!(fenny::first_larger(&tree, root, 27-1), Some(5));``````

### Flavors

The aforementioned functions come in a whole lot of flavors. In addition to the plain ones there are _2d, _3d, _so, _so_2d_lex and _so_3d_lex. You must query using the same flavor that you update with.

#### Slope-offset

⚠️ Slope-offset functions use negative numbers and multiplications internally, select your value-type with this in mind.

The _so flavor uses two Fenwick trees. That lets it support the range update.

``a[i..=j] += v;``

which is performed like so

``````let mut slope = vec![0; size];
let mut offset = vec![0; size];
fenny::update_so(&mut slope, &mut offset, i..=j, v);``````

#### 2d / 3d

A 2d (3d) tree is used to represent a 2d(3d) array. The prefix sum for a given point p is over all points in the box defined by p and the origin. These flavors don’t support first_larger. The runtime of update and psum are log(size_z) * log(size_y) * log(size_x).

``````use fenny::*;
let dim = Dim2{y: 5, x: 8};
let mut tree = vec![0; dim.y * dim.x];
update_2d(&mut tree, dim , Point2{y: 3, x: 6}, 7);
assert_eq!(psum_2d(&tree, dim, Point2{y: 2, x: 6}), 0);
assert_eq!(psum_2d(&tree, dim, Point2{y: 3, x: 5}), 0);
assert_eq!(psum_2d(&tree, dim, Point2{y: 3, x: 6}), 7);
assert_eq!(psum_2d(&tree, dim, Point2{y: 4, x: 7}), 7);``````

#### Slope-offset, 2d/3d, lexicographic

These flavor uses one tree per dimension to store slope, and one additional tree to store the offset. The uppdate functions operate on a box defined by two points. The psum on the other hand sums in lexicographic order. As first_larger looks for a large enough psum, it too operates in lexicographic order. The runtime of update, psum and first_larger are log(size_z) * log(size_y) * log(size_x).

``````use fenny::*;
let dim = Dim3{z: 12, y: 6, x: 8};
let mut slope_z = vec![0i64; dim.z];
let mut slope_y = vec![0i64; dim.z * dim.y];
let mut slope_x = vec![0i64; dim.z * dim.y * dim.x];
let mut offset  = vec![0i64; dim.z * dim.y * dim.x];
let p0 = Point3{z: 3, y: 2, x: 1};
let p1 = Point3{z: 7, y: 5, x: 5};
update_so_3d_lex(&mut slope_z, &mut slope_y, &mut slope_x, &mut offset, dim, p0, p1, 11);
// (4, 0, 0) comes after (3, 2, 1), (3, 2, 2), ... (3, 5, 5)
let p2 = Point3{z: 4, y: 0, x: 0};
assert_eq!(psum_so_3d_lex(&slope_z, &slope_y, &slope_x, &offset, dim, p2), 5 * 4 * 11);
// (4, 0, 0) has a psum of 5*4*11, but so does (3, 5, 5).
assert_eq!(first_larger_so_3d_lex(&slope_z, &slope_y, &slope_x, &offset, dim,
5 * 4 * 11 - 1), Some(Point3{z:3, y: 5, x: 5}));``````

## Structs

The size of a 2d Fenwick tree.

The size of a 3d Fenwick tree.

An index into a 2d array.

An index into a 3d array.

## Traits

Trait used for all functions in this crate.

## Functions

Finds the smallest `i` so that `val < a[i]`

Finds the smallest `i` so that `val < a[i]`

Finds the lexicographically first `(y, x)` such that `val < a[y][x]`

Finds the lexicographically first `(z, y, x)` such that `val < a[z][y][x]`

Finds the root index, plus one, for a tree of `size`.

Computes `sum(a[x])` for `x <= ind`.

Computes a 2d-prefix sum.

Computes a 3d-prefix sum.

Computes `sum(a[x])` for `x <= ind`.

Computes a 2d lexicographic prefix sum.

Computes a 3d lexicographic prefix sum.

Updates `a[ind] += val`

Updates `a[p.y][p.x] += val`

Updates `a[p.z][p.y][p.x] += val`.

Updates `a[i..=j] += val`

Updates `a[y][x] += val` for all `(y,z) ∈ box(p0, p1)`

Updates `a[z][y][x] += val` for all `(z,y,z) ∈ box(p0, p1)`