binary-indexed-tree

Binary Indexed Tree(aka Fenwick Tree) implementation

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
binary-indexed-tree
670.5.0a year ago7 years agoMinified + gzip package size for binary-indexed-tree in KB

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

*   [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

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

Returns
number value of first target, or undefined O(N \* log(N))

findIndex

linear search.
Parameters

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

indexOf

linear search.
Parameters
Function? equality function (optional, default defaultEqual)
Returns number index of first target, or -1 O(N \* log(N))

lastIndexOf

linear search.
Parameters
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
Function? (optional, default defaultCompare)
Returns number index of lower-bound O(log(N))

upperBound

find upper bound. SEQUENCE MUST BE STRICTLY SORTED.
Parameters
Function? (optional, default 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 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.