fast-binary-indexed-tree
A JavaScript implementation of Binary Indexed Tree with fast initialization
Binary Indexed Tree also known as Fenwick tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values.
This JavaScript implementation is based on the Top Coder article by boba5551. Most of the terms respect to the author's definition except for
- All indexes in the public API are 0 based
There's another implementation by berlysia. Comparing to that, this
one is faster for creation. The constructor accepts a defaultFrequency
option,
which initializes all frequencies in O(1) time complexity.
Installation
$ npm install --save fast-binary-indexed-tree
Usage
Refer to the document for details.
var BinaryIndexedTree = ; var bit = defaultFrequency: 10 maxVal: 10 ; // Read a single frequency// Output: 10console; // Update the frequency by delta// Output: 15bit;console; // Write a single frequency// Output: 20bit;console; // Read the cumulated frequency// Output: 55console; // Find the lower bound// Output: 3console; // Find the upper bound// Output: 4console;
License
MIT
This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.