Crate fenwick_tree

Source
Expand description

The crate contains a binary indexed tree (Fenwick tree) implementation and some of the extensions for it.

The general idea of the Fenwick tree is that it allows for both queries and updates of partial sums to be performed in O(log n) time.

For more details, see Explanation section.

For tree API, see FenwickTree struct.

§Examples

Constructing a new tree that is equal to [1, 2, 3] array.

use fenwick_tree::FenwickTree;

let mut tree = FenwickTree::<i32>::with_len(3);

// `add` has time complexity O(log n).
tree.add(0, 1).unwrap(); // Adds `1` to element at `0`.
tree.add(1, 2).unwrap(); // Adds `2` to element at `1`.
tree.add(2, 3).unwrap(); // Adds `3` to element at `2`.

Calculating all possible partial sums of the tree above.

// `sum` has time complexity O(log n).
assert_eq!(tree.sum(0..1).unwrap(), 1);
assert_eq!(tree.sum(0..2).unwrap(), 3);
assert_eq!(tree.sum(0..3).unwrap(), 6);

assert_eq!(tree.sum(1..2).unwrap(), 2);
assert_eq!(tree.sum(1..3).unwrap(), 5);

assert_eq!(tree.sum(2..3).unwrap(), 3);

sum accepts RangeBounds, so actually you can use any syntax you’d like.

assert_eq!(tree.sum(..).unwrap(), 6);
assert_eq!(tree.sum(0..).unwrap(), 6);
assert_eq!(tree.sum(..3).unwrap(), 6);
assert_eq!(tree.sum(..=2).unwrap(), 6);
assert_eq!(tree.sum(0..=2).unwrap(), 6);

For error handling, see AddError and SumError structs.

§Explanation

In this section, an explanation about the tree implementation is provided.

§Indexing

The easiest explanation considers that indexing of the array is one-based (as in the original paper).

Sums are stored in the array by the following rule: an item with index i stores a cumulative sum of [i - g(i), i] range, where g(i) = i & (-i) or the size of the range covered by i.

This looks a bit scary but the whole intuition behind Fenwick tree is very simple: the position of the first 1 bit in the i defines the value of g(i).

  • i = 4 = 100, g(i) = 100 (4) or [1, 4] range (note one-based indexing)
  • i = 3 = 011, g(i) = 001 (1) or [3, 3] range
  • i = 2 = 010, g(i) = 010 (2) or [1, 2] range
  • i = 1 = 001, g(i) = 001 (1) or [1, 1] range

§Querying

Prefix sum of n items consists of sum of some number of ranges, depending on n.

  • n = 4 sum of [1, 4] (4 index)
  • n = 3 sum of [3, 3] (3 index) and [1, 2] (2 index)
  • n = 2 sum of [1, 2] (2 index)
  • n = 1 sum of [1, 1] (1 index)

In order to calculate a prefix sum, we need to traverse the array from right to left, decreasing i by g(i).

  • i = 100 (4), i - g(i) = 000 (0)
  • i = 011 (3), i - g(i) = 010 (2)
  • i = 010 (2), i - g(i) = 000 (0)
  • i = 001 (1), i - g(i) = 000 (0)

So, how g(i) is calculated? This can easily be done by using the representation of negative numbers in two’s complement systems, where -i means !i + 1.

let i = any_number();
assert_eq!(!i + 1, -i);

In binary, !i inverts all bits in the i, and !i + 1 flips all bits up to first 0.

  • i = 001, !i = 110, -i = 111
  • i = 010, !i = 101, -i = 110
  • i = 011, !i = 100, -i = 101
  • i = 100, !i = 011, -i = 100

This means that i and -i have all bits different except the first 1 bit. So, g(i) is as simple as i & (-i).

§Updating

Updating a value at i means traversing the array from left to right, updating ranges that contain the value.

Here similar logic applies as for querying: we need to increase i by g(i).

  • i = 4 = 100, i + g(i) = 1000 (8)
  • i = 3 = 011, i + g(i) = 0100 (4)
  • i = 2 = 010, i + g(i) = 0100 (4)
  • i = 1 = 001, i + g(i) = 0010 (2)

That’s it!

§Notes

The explanation above assumes one-based indexing, however, in Rust, as in most other programming languages, indexing is zero-based. Thus, it’s not that easy to calculate i & (-i) if i is of usize.

For the sake of code simplicity and performance, the following changes were made:

  • querying is one-based: i & (i - 1)
  • updating is zero-based: i | (i + 1)

§References

Structs§

  • FenwickTree
    An implementation of the binary indexed tree (Fenwick tree) data structure.

Enums§

  • AddError
    An error in adding a delta to a tree element.
  • SumError
    An error in calculating a partial sum.