Skip to content

berlysia/binary-indexed-tree-js

Repository files navigation

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

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

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
  • 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

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.

  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.

About

Binary Indexed Tree implementation in JavaScript.

Resources

Stars

Watchers

Forks

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •