Source: FenwickTree.js

/**
 * Fenwick Tree, またはBinary Indexed Tree
 * 
 * http://hos.ac/slides/20140319_bit.pdf
 * とりあえず基本的な機能のみ実装する。
 * N個の数値v1, v2, ... , vnに対して、
 * vaに値wを加えるadd(a, w)
 * v1, v2, ..., vaまでの和を求める
 * この2つの計算をO(log N)で行う。
 * 
 * このクラスでデータの添え字は1-indexedで扱われることに注意する。
 * 
 */
class FenwickTree {

    /**
     * 
     * @param {number} N FenwickTreeで管理する数値データの個数。正の整数でなければならない。
     */
    constructor(N) {
        N = N || 1000000; //Nが与えられなかったときはN = 10^6で初期化しておく
        this.size = N;

        //ノードの値を格納する配列。
        //数値の値は1-indexedで管理される。
        //this.nodes[i]は、iで終わる区間の和を保持する。
        this.nodes = [];
        for (let i = 0; i < N + 10; i++) {
            this.nodes[i] = 0;
        }
        //ここはもう少しきれいに実装したい
    }

    /**
     * 数値の配列からFenwickTreeを初期化して返却する。
     * 
     * @param {number[]} valueArray 数値の配列。この配列は0-indexedであるものとする。
     * @returns {FenwickTree} 数値配列によって初期化されたFenwickTree
     */
    static fromArray(valueArray) {
        const ft = new FenwickTree(valueArray.length);
        for (let i = 0; i < valueArray.length; i++) {
            ft.add(i + 1, valueArray[i]); //FenwickTreeは1-indexedでデータ管理することに注意
        }
        return ft;
    }

    /**
     * 指定した位置のデータに指定した値を加算する。
     * 
     * @param {number} index 値を加算する対象のインデックス
     * @param {number} value 整数または浮動小数点数
     * @returns {void}
     */
    add(index, value) {
        //node[index]を更新して、そのノードが管理する区間の幅だけindexを増やす。
        for (let x = index; x <= this.size; x += x & -x) {
            this.nodes[x] += value;
        }
    }

    /**
     * v1からv_indexまでの総和を計算する。
     * 
     * @param {number} index 1以上N以下の整数でなければならない。
     * @returns {number} v1 + v2 + ... + v_index
     */
    sumUpto(index) {
        let sum = 0;
        for (let x = index; x > 0; x -= x & -x) {
            sum += this.nodes[x];
        }
        return sum;
    }

    /**
     * 閉区間[min,max]におけるデータの総和を計算する。
     * 
     * min > maxとしたときの動作は未定義。
     * 
     * @param {number} min 1以上N以下の整数
     * @param {number} max 1以上N以下の整数
     * @returns {number} v_min + ... + v_max
     */
    sum(min,max) {
        return this.sumUpto(max) - this.sumUpto(min-1);
    }
}

module.exports = FenwickTree;