-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Binary Indexed Trees (a.k.a. Fenwick Trees).
--   
--   Binary indexed trees are a data structure on indexes 1 through n. They
--   allow you to compute the sum of all values at indexes 1 through i in
--   O(logn) and to increase the value at index i in O(logn).
--   
--   This implements binary indexed trees, both as an immutable data
--   structure in pure code and as a mutable data structure using the ST
--   Monad.
--   
--   Both the immutable and mutable version have the same runtime
--   complexity, but the mutable version has a smaller constant.
--   
--   Written by Maxwell Sayles (2012).
@package binary-indexed-tree
@version 0.1


-- | 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) "<i>A new data structure
--   for cumulative frequency tables</i>"
--   <a>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917</a>.
--   
--   Index i in the tree represents the sum of all values of indexes
--   j&lt;=i for some array.
--   
--   Indexes start at 1.
module Data.BinaryIndexedTree.ST

-- | Binary Indexed Tree
type BinaryIndexedTree s = STUArray s Int Int

-- | Construct a new binary indexed tree on the indexes 1 through n.
new :: Int -> ST s (BinaryIndexedTree s)

-- | Compute the sum of all indexes 1 through i, inclusive. Takes O(logn).
(!) :: BinaryIndexedTree s -> Int -> ST s Int

-- | Increment the value at index i. Takes O(logn).
increment :: Int -> Int -> BinaryIndexedTree s -> ST s ()


-- | Implements persistent binary indexed trees (or Fenwick Trees) in
--   <i>O(logn)</i> for increment and lookup and <i>O(n)</i> for creation.
--   
--   Index <i>i</i> in the tree represents the sum of all values of indexes
--   <i>j&lt;=i</i> for some array.
--   
--   The idea is that for <i>k</i> bits, we parse the index <i>i</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 <i>&gt;=</i> than the
--   index <i>i</i>.
--   
--   <i>Note: I was unable to find the algorithm used here in the
--   literature.</i>
module Data.BinaryIndexedTree

-- | A Binary indexed tree.
data BinaryIndexedTree a

-- | Construct a binary indexed tree on k bits. Takes O(n).
new :: Num a => Int -> BinaryIndexedTree a

-- | Lookup the sum of all values from index 1 to index i. Takes O(logn).
(!) :: Num a => BinaryIndexedTree a -> Int -> a

-- | Increment the value at index i by amount x. Takes O(logn).
increment :: Num a => Int -> a -> BinaryIndexedTree a -> BinaryIndexedTree a