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
  • Parameters
  • length
  • add
    • Parameters
  • update
    • Parameters
  • original
    • Parameters
  • get
    • Parameters
  • prefix
    • Parameters
  • sum
  • find
    • Parameters
  • findIndex
    • Parameters
  • indexOf
    • Parameters
  • lastIndexOf
    • Parameters
  • lowerBound
    • Parameters
  • upperBound
    • Parameters
  • toArray
  • build
    • Parameters

BinaryIndexedTree

BinaryIndexedTree implementation

Parameters

• size number

length

Type: number

Returns number size of BIT

add

Parameters

• idx number should be less than size of BIT
• val number

Returns boolean successfully added or not O(log(N))

update

Parameters

• idx number should be less than size of BIT
• val number

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 value
• equal Function? equality function (optional, default defaultEqual)

Returns number index of first target, or -1 O(N * log(N))

lastIndexOf

linear search.

Parameters

• target number value
• equal Function? equality function (optional, default defaultEqual)

Returns number index of last target, or -1 O(N * log(N))

lowerBound

find lower bound. SEQUENCE MUST BE STRICTLY SORTED.

Parameters

• target number
• comp Function? (optional, default defaultCompare)

Returns number index of lower-bound O(log(N))

upperBound

find upper bound. SEQUENCE MUST BE STRICTLY SORTED.

Parameters

• target number
• comp Function? (optional, default defaultCompare)

Returns number index of upper-bound O(log(N))

toArray

Returns Array<number> array of cusum O(N)

build

Parameters

• seed Array<number> BIT will be built from this array

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.

1. Fork it!
2. Create your feature branch: git checkout -b my-new-feature
3. Commit your changes: git commit -am 'Add some feature'
4. Push to the branch: git push origin my-new-feature
5. Submit a pull request :D

License

Copyright © 2016-present berlysia. Licensed under the MIT license.