Portability | portable |
---|---|

Stability | stable |

Maintainer | maxwellsayles@gmail.com |

Safe Haskell | Safe-Inferred |

Implements persistent binary indexed trees (or Fenwick Trees)
in *O(logn)* for increment and lookup and *O(n)* for creation.

Index *i* in the tree represents the sum of all values of
indexes *j<=i* for some array.

The idea is that for *k* bits, we parse the index *i* from msb
to lsb and move left/right on the tree for 0/1.

For a read, we accumulate the values in the tree where the binary representation of the index contains a 1. (The technique is similar to binary exponentiation.)

For an increment, we should increment parent nodes
in the tree whose corresponding binary index representation
is *>=* than the index *i*.

*Note: I was unable to find the algorithm used here in the literature.*

- data BinaryIndexedTree a
- new :: Num a => Int -> BinaryIndexedTree a
- (!) :: Num a => BinaryIndexedTree a -> Int -> a
- increment :: Num a => Int -> a -> BinaryIndexedTree a -> BinaryIndexedTree a

# Documentation

data BinaryIndexedTree a Source

A Binary indexed tree.

new :: Num a => Int -> BinaryIndexedTree aSource

Construct a binary indexed tree on k bits. Takes O(n).

(!) :: Num a => BinaryIndexedTree a -> Int -> aSource

Lookup the sum of all values from index 1 to index i. Takes O(logn).

increment :: Num a => Int -> a -> BinaryIndexedTree a -> BinaryIndexedTree aSource

Increment the value at index i by amount x. Takes O(logn).