Fenwick tree

fenwick.go

// https://en.wikipedia.org/wiki/Fenwick_tree
// https://www.youtube.com/watch?v=uSFzHCZ4E-8

type FenwickTree []int

// returns sum of all elements up to index 'i'
func (ft FenwickTree) sum(i int) int {
    res := 0
    for ; i > 0; i -= lsb(i) {
        res += ft[i]
    }
    return res
}

// adds value 'n' to index 'i' and propogates updates across the Fenwick Tree
func (ft FenwickTree) add(i, n int) {
    for ; i < len(ft); i += lsb(i) {
        ft[i] += n
    }
}

// least significant bit / last set bit; used by FenwickTree
func lsb(n int) int { return n & (-n) }