binary-indexed-tree (empty) → 0.1
raw patch · 5 files changed
+338/−0 lines, 5 filesdep +arraydep +basesetup-changed
Dependencies added: array, base
Files
- Data/BinaryIndexedTree.hs +78/−0
- Data/BinaryIndexedTree/ST.hs +60/−0
- LICENSE +165/−0
- Setup.hs +2/−0
- binary-indexed-tree.cabal +33/−0
+ Data/BinaryIndexedTree.hs view
@@ -0,0 +1,78 @@+{- |+Module : Data.BinaryIndexedTree+Description : Binary Indexed Trees (a.k.a. Fenwick Trees)+Copyright : (c) 2012 Maxwell Sayles.+License : LGPL++Maintainer : maxwellsayles@gmail.com+Stability : stable+Portability : portable++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./+-}++module Data.BinaryIndexedTree+ (BinaryIndexedTree, new, (!), increment)+where++import Data.Bits++{-| A Binary indexed tree. -}+data BinaryIndexedTree a = BinaryIndexedTree Int (Tree a)++data Tree a = Empty | Node a (Tree a) (Tree a)++{-| +Construct a binary indexed tree on k bits. Takes O(n).+-}+new :: Num a => Int -> BinaryIndexedTree a+new k = BinaryIndexedTree k $ f k+ where f 0 = Empty+ f k = Node 0 (f (k - 1)) (f (k - 1))++{-|+Lookup the sum of all values from index 1 to index i. Takes O(logn).+-}+(!) :: Num a => BinaryIndexedTree a -> Int -> a+(!) (BinaryIndexedTree k root) i = f root (k - 1) 0+ where f Empty _ acc = acc+ f (Node x l r) j acc+ | i `testBit` j = acc' `seq` f l j' acc'+ | otherwise = f r j' acc+ where j' = j - 1+ acc' = acc + x++{-|+Increment the value at index i by amount x. Takes O(logn).+-}+increment :: Num a => Int -> a -> BinaryIndexedTree a -> BinaryIndexedTree a+increment i x (BinaryIndexedTree k root) =+ BinaryIndexedTree k $ f root (k - 1) 0+ where f (Node y l r) j acc+ | i `testBit` j =+ if acc' == i+ then y' `seq` Node y' l r+ else acc' `seq` Node y (f l j' acc') r+ | otherwise = y' `seq` Node y' l (f r j' acc)+ where y' = x + y+ j' = j - 1+ acc' = acc `setBit` j++
+ Data/BinaryIndexedTree/ST.hs view
@@ -0,0 +1,60 @@+{-|+Module : Data.BinaryIndexedTree.ST+Description : Binary Indexed Trees (a.k.a. Fenwick Trees)+Copyright : (c) 2012 Maxwell Sayles.+License : LGPL++Maintainer : maxwellsayles@gmail.com+Stability : stable+Portability : portable++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.+-}++module Data.BinaryIndexedTree.ST+ (BinaryIndexedTree, new, (!), increment)+where++import Control.Applicative+import Control.Monad+import Control.Monad.ST+import Data.Array.MArray+import Data.Array.ST+import Data.Bits++{-| 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)+new n = newListArray (1, n) $ repeat 0++{-| Compute the sum of all indexes 1 through i, inclusive. Takes O(logn). -}+(!) :: BinaryIndexedTree s -> Int -> ST s Int+(!) bit i = f i 0+ where f i acc+ | i < 1 = return acc+ | otherwise =+ do acc' <- (+acc) <$> readArray bit i+ let i' = i - (i .&. (-i))+ f i' acc'++{-| Increment the value at index i. Takes O(logn). -}+increment :: Int -> Int -> BinaryIndexedTree s -> ST s ()+increment i v bit =+ do (_, u) <- getBounds bit+ let f i = when (i <= u) $ do+ writeArray bit i . (+v) =<< readArray bit i+ let i' = i + (i .&. (-i))+ f i'+ f i
+ LICENSE view
@@ -0,0 +1,165 @@+ GNU LESSER GENERAL PUBLIC LICENSE+ Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.+++ This version of the GNU Lesser General Public License incorporates+the terms and conditions of version 3 of the GNU General Public+License, supplemented by the additional permissions listed below.++ 0. Additional Definitions.++ As used herein, "this License" refers to version 3 of the GNU Lesser+General Public License, and the "GNU GPL" refers to version 3 of the GNU+General Public License.++ "The Library" refers to a covered work governed by this License,+other than an Application or a Combined Work as defined below.++ An "Application" is any work that makes use of an interface provided+by the Library, but which is not otherwise based on the Library.+Defining a subclass of a class defined by the Library is deemed a mode+of using an interface provided by the Library.++ A "Combined Work" is a work produced by combining or linking an+Application with the Library. The particular version of the Library+with which the Combined Work was made is also called the "Linked+Version".++ The "Minimal Corresponding Source" for a Combined Work means the+Corresponding Source for the Combined Work, excluding any source code+for portions of the Combined Work that, considered in isolation, are+based on the Application, and not on the Linked Version.++ The "Corresponding Application Code" for a Combined Work means the+object code and/or source code for the Application, including any data+and utility programs needed for reproducing the Combined Work from the+Application, but excluding the System Libraries of the Combined Work.++ 1. Exception to Section 3 of the GNU GPL.++ You may convey a covered work under sections 3 and 4 of this License+without being bound by section 3 of the GNU GPL.++ 2. Conveying Modified Versions.++ If you modify a copy of the Library, and, in your modifications, a+facility refers to a function or data to be supplied by an Application+that uses the facility (other than as an argument passed when the+facility is invoked), then you may convey a copy of the modified+version:++ a) under this License, provided that you make a good faith effort to+ ensure that, in the event an Application does not supply the+ function or data, the facility still operates, and performs+ whatever part of its purpose remains meaningful, or++ b) under the GNU GPL, with none of the additional permissions of+ this License applicable to that copy.++ 3. Object Code Incorporating Material from Library Header Files.++ The object code form of an Application may incorporate material from+a header file that is part of the Library. You may convey such object+code under terms of your choice, provided that, if the incorporated+material is not limited to numerical parameters, data structure+layouts and accessors, or small macros, inline functions and templates+(ten or fewer lines in length), you do both of the following:++ a) Give prominent notice with each copy of the object code that the+ Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the object code with a copy of the GNU GPL and this license+ document.++ 4. Combined Works.++ You may convey a Combined Work under terms of your choice that,+taken together, effectively do not restrict modification of the+portions of the Library contained in the Combined Work and reverse+engineering for debugging such modifications, if you also do each of+the following:++ a) Give prominent notice with each copy of the Combined Work that+ the Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the Combined Work with a copy of the GNU GPL and this license+ document.++ c) For a Combined Work that displays copyright notices during+ execution, include the copyright notice for the Library among+ these notices, as well as a reference directing the user to the+ copies of the GNU GPL and this license document.++ d) Do one of the following:++ 0) Convey the Minimal Corresponding Source under the terms of this+ License, and the Corresponding Application Code in a form+ suitable for, and under terms that permit, the user to+ recombine or relink the Application with a modified version of+ the Linked Version to produce a modified Combined Work, in the+ manner specified by section 6 of the GNU GPL for conveying+ Corresponding Source.++ 1) Use a suitable shared library mechanism for linking with the+ Library. A suitable mechanism is one that (a) uses at run time+ a copy of the Library already present on the user's computer+ system, and (b) will operate properly with a modified version+ of the Library that is interface-compatible with the Linked+ Version.++ e) Provide Installation Information, but only if you would otherwise+ be required to provide such information under section 6 of the+ GNU GPL, and only to the extent that such information is+ necessary to install and execute a modified version of the+ Combined Work produced by recombining or relinking the+ Application with a modified version of the Linked Version. (If+ you use option 4d0, the Installation Information must accompany+ the Minimal Corresponding Source and Corresponding Application+ Code. If you use option 4d1, you must provide the Installation+ Information in the manner specified by section 6 of the GNU GPL+ for conveying Corresponding Source.)++ 5. Combined Libraries.++ You may place library facilities that are a work based on the+Library side by side in a single library together with other library+facilities that are not Applications and are not covered by this+License, and convey such a combined library under terms of your+choice, if you do both of the following:++ a) Accompany the combined library with a copy of the same work based+ on the Library, uncombined with any other library facilities,+ conveyed under the terms of this License.++ b) Give prominent notice with the combined library that part of it+ is a work based on the Library, and explaining where to find the+ accompanying uncombined form of the same work.++ 6. Revised Versions of the GNU Lesser General Public License.++ The Free Software Foundation may publish revised and/or new versions+of the GNU Lesser General Public License from time to time. Such new+versions will be similar in spirit to the present version, but may+differ in detail to address new problems or concerns.++ Each version is given a distinguishing version number. If the+Library as you received it specifies that a certain numbered version+of the GNU Lesser General Public License "or any later version"+applies to it, you have the option of following the terms and+conditions either of that published version or of any later version+published by the Free Software Foundation. If the Library as you+received it does not specify a version number of the GNU Lesser+General Public License, you may choose any version of the GNU Lesser+General Public License ever published by the Free Software Foundation.++ If the Library as you received it specifies that a proxy can decide+whether future versions of the GNU Lesser General Public License shall+apply, that proxy's public statement of acceptance of any version is+permanent authorization for you to choose that version for the+Library.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ binary-indexed-tree.cabal view
@@ -0,0 +1,33 @@+Name: binary-indexed-tree+Version: 0.1+Synopsis: Binary Indexed Trees (a.k.a. Fenwick Trees).+Description: 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).+License: LGPL+License-file: LICENSE+Author: Maxwell Sayles <maxwellsayles@gmail.com>+Maintainer: Maxwell Sayles <maxwellsayles@gmail.com>+Category: Data+Build-type: Simple+Stability: Stable+Cabal-version: >= 1.8++Library+ Exposed-modules: Data.BinaryIndexedTree,+ Data.BinaryIndexedTree.ST+ Build-depends: base >= 3 && < 5,+ array >= 0.3++