Data.BinaryIndexedTree

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.

Documentation

data BinaryIndexedTree a

A Binary indexed tree.

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

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

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

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

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

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