fenwick-tree
v0.0.0
Published
Compute prefix sums of arrays in O(log n)
Downloads
9
Readme
fenwick-tree
A Fenwick tree is a data structure for maintaining prefix sums under incremental updates. This module is a simple array based implementation of this concept.
Example
var fenwick = require("fenwick-tree")
//Build tree:
var tree = fenwick([1, 5, -1, 0, 5])
for(var i=0; i<5; ++i) {
console.log(fenwick.query(tree, i))
}
//Prints out:
// 1
// 6
// 5
// 5
// 10
//Add 3 to the element at index 2
fenwick.update(tree, 2, 3)
//Prints out:
// 1
// 6
// 8
// 8
// 13
API
var fenwick = require("fenwick-tree")
fenwick(array[, out])
Initializes a Fenwick tree in O(array.length log(array.length))
time.
array
is an array of numbersout
is an optional array that gets the resulting Fenwick tree. Can be any array like data structure, such as a typed array or native array. If not specified anArray
is allocated
Returns out
or the allocated Array
fenwick.query(tree, at)
Compute the prefix sum up to at
tree
is the Fenwick tree arrayat
is the index we are querying at
Returns The sum of all elements in the tree with index <= at
fenwick.update(tree, at, by)
Adds an offset to the Fenwick tree of by
at index at
.
tree
is the Fenwick tree arrayat
is the index to updateby
is the amount to add to the tree
Credits
Based on the first part of the following blog post by Petr Mitrichev:
http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html
JS implementation by Mikola Lysenko. MIT License