Binary Indexed Tree
Binary Indexed Tree(aka Fenwick Tree) implementationInstall
Install with npm:$ npm install binary-indexed-tree
BIT?
Binary Indexed Tree (aka Fenwick Tree) is a data structure providing efficient methods for prefix-sum.API
Table of Contents
* [Parameters](#parameters)
* [length](#length)
* [add](#add)
* [Parameters](#parameters-1)
* [update](#update)
* [Parameters](#parameters-2)
* [original](#original)
* [Parameters](#parameters-3)
* [get](#get)
* [Parameters](#parameters-4)
* [prefix](#prefix)
* [Parameters](#parameters-5)
* [sum](#sum)
* [find](#find)
* [Parameters](#parameters-6)
* [findIndex](#findindex)
* [Parameters](#parameters-7)
* [indexOf](#indexof)
* [Parameters](#parameters-8)
* [lastIndexOf](#lastindexof)
* [Parameters](#parameters-9)
* [lowerBound](#lowerbound)
* [Parameters](#parameters-10)
* [upperBound](#upperbound)
* [Parameters](#parameters-11)
* [toArray](#toarray)
* [build](#build)
* [Parameters](#parameters-12)
BinaryIndexedTree
BinaryIndexedTree implementationParameters
size
number
length
Type: numberReturns number size of BIT
add
Parameters
idx
number should be less than size of BITval
Returns boolean successfully added or not O(log(N))
update
Parameters
idx
number should be less than size of BITval
Returns boolean successfully updated or not O(log(N))
original
Parameters
idx
number should be less than size of BIT
Returns number original value of array O(log(N))
get
Parameters
idx
number should be less than size of BIT
Returns number sum of range \[0..idx O(log(N))
prefix
Parameters
idx
number should be less than size of BIT
Returns number sum of range \[0..idx) O(log(N))
sum
Returns number sum of all O(log(N))find
linear search.Parameters
check
Function function
Returns number value of first target, or undefined O(N \* log(N))
findIndex
linear search.Parameters
check
Function function
Returns number index of first target, or -1 O(N \* log(N))
indexOf
linear search.Parameters
target
number valueequal
defaultEqual
)Returns number index of first target, or -1 O(N \* log(N))
lastIndexOf
linear search.Parameters
target
number valueequal
defaultEqual
)Returns number index of last target, or -1 O(N \* log(N))
lowerBound
find lower bound. SEQUENCE MUST BE STRICTLY SORTED.Parameters
target
numbercomp
defaultCompare
)Returns number index of lower-bound O(log(N))
upperBound
find upper bound. SEQUENCE MUST BE STRICTLY SORTED.Parameters
target
numbercomp
defaultCompare
)Returns number index of upper-bound O(log(N))
toArray
Returns Array<number> array of cusum O(N)build
Parameters
Returns BinaryIndexedTree instance O(N)
Changelog
Read the CHANGELOG.Running tests
Install devDependencies and Runnpm test
:$ npm -d it
Contributing
Pull requests and stars are always welcome. For bugs and feature requests, please create an issue.- Fork it!
- Create your feature branch:
git checkout -b my-new-feature
- Commit your changes:
git commit -am 'Add some feature'
- Push to the branch:
git push origin my-new-feature
- Submit a pull request :D