indexed-trees.js

// For more info about indexed trees visit
// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
//
// Sample run:
// var tree = new IndexedTree([2, 5, 6, 9])
// tree.getSumIn(2, 3) -> 15
//
// Why this is cool? It gives the sum of the values of a subarray in O(log n) time, 
// the update of a value also runs in O(log n)

function IndexedTree(list) {
    var listSize = list.length;
    this._sum = new Array(listSize + 1);
    
    // build the tree
    for (var i = 0; i <= listSize; i++) {
        this._sum[i] = 0;
    }
    for (var i = 0; i < listSize; i++) {
        this.update(i + 1, list[i])
    }
}

IndexedTree.prototype = {
    update: function(i, sum) {
        var sumListSize = this._sum.length;
        while (i < sumListSize) {
            this._sum[i] += sum;
            i = i + (i & -i);
        }
    },
    getSum: function(i) {
        var sum = 0;
        i = i + 1;
        while (i > 0) {
            sum += this._sum[i];
            // remove the last bit set from i
            i = i - (i & -i);
        }
        return sum;
    },
    getSumInRange: function(i, j) {
        return this.getSum(j) - this.getSum(i-1); 
    }
}