binary-indexed-tree-0.1: Binary Indexed Trees (a.k.a. Fenwick Trees).

Safe HaskellNone



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"

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

Indexes start at 1.



type BinaryIndexedTree s = STUArray s Int IntSource

Binary Indexed Tree

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

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

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

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

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

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