binary-indexed-tree
v0.5.0
Published
Binary Indexed Tree(aka Fenwick Tree) implementation
Downloads
574
Readme
Binary Indexed Tree
Binary Indexed Tree(aka Fenwick Tree) implementation
Install
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
BinaryIndexedTree
BinaryIndexedTree implementation
Parameters
size
number
length
Type: number
Returns number size of BIT
add
Parameters
Returns boolean successfully added or not O(log(N))
update
Parameters
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
Returns number index of first target, or -1 O(N * log(N))
lastIndexOf
linear search.
Parameters
Returns number index of last target, or -1 O(N * log(N))
lowerBound
find lower bound. SEQUENCE MUST BE STRICTLY SORTED.
Parameters
Returns number index of lower-bound O(log(N))
upperBound
find upper bound. SEQUENCE MUST BE STRICTLY SORTED.
Parameters
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 Run npm 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
License
Copyright © 2016-present berlysia. Licensed under the MIT license.