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](#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 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.