Data.BinaryIndexedTree.ST

Implements mutable binary indexed trees (a.k.a. Fenwick Trees) in O(logn) for increment and lookup and O(n) for creation.

Original concept from Peter M. Fenwick (1994) "A new data structure for cumulative frequency tables" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917.

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

Indexes start at 1.

Documentation

type BinaryIndexedTree s = STUArray s Int Int

Binary Indexed Tree

new :: Int -> ST s (BinaryIndexedTree s)

Construct a new binary indexed tree on the indexes 1 through n.

(!) :: BinaryIndexedTree s -> Int -> ST s Int

Compute the sum of all indexes 1 through i, inclusive. Takes O(logn).

increment :: Int -> Int -> BinaryIndexedTree s -> ST s ()

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