FenwickTree.fs

// http://www.prefield.com/algorithm/container/fenwick_tree.html
// add(k, a) == v[k] = v[k] + a
// sum(i, j) == v[i] + ... + v[j] (両端を含む)
type FenwickTree(N : int) =
    let zero = LanguagePrimitives.GenericZero
    let x = Array.create N zero
    member me.sum i j =
        if i = 0 then
            let rec loop acc k =
                if k >= 0 then loop (acc + x.[k]) ((k &&& (k+1)) - 1)
                else acc
            loop zero j
        else
            me.sum 0 j - me.sum 0 (i-1)
    member me.add i a =
        let rec loop k =
            if k < x.Length then
                x.[k] <- x.[k] + a
                loop (k ||| (k+1))
        loop i