Simple Fenwick tree implementation
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


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.


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


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 numbers
  • out 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 an Array is allocated

Returns out or the allocated Array

fenwick.query(tree, at)

Compute the prefix sum up to at

  • tree is the Fenwick tree array
  • at 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 array
  • at is the index to update
  • by is the amount to add to the tree


Based on the first part of the following blog post by Petr Mitrichev:

JS implementation by Mikola Lysenko. MIT License