N-dimensional Binary Indexed Tree

Provides logarithmic time prefix-sums and updates to numeric data sets in 1, 2, 3, or more dimensions.

Check out Stack Overflow, Wikipedia, and TopCoder for an overview of the data structure in one dimension. GeeksForGeeks has a useful explanation of multi-dimensional generalization, but beware of buggy code.

Getting Started

Install from NPM

$ npm install nd-binary-indexed-tree

Examples

const BITree = require('nd-binary-indexed-tree');
let biTree = new BITree({initialValues: [
  [3,  1, 5  ],
  [0, -1, 9.5],
  [4,  4, 90 ]
]});
biTree.sumPrefix([2, 1]); // 11
biTree.adjust([1, 1], +2);
biTree.sumPrefix([2, 1]); // 13
;

See tests for more examples.