Function NewFenwickTree

structure/fenwicktree/fenwicktree.go:20–34

NewFenwickTree creates a new Fenwick tree, initializes bit with the values of the array. Note that the queries and updates should have one based indexing.

(array []int)

// the values of the array. Note that the queries and updates should have
// one based indexing.
func NewFenwickTree(array []int) *FenwickTree {
	newArray := []int{0} // Appending a 0 to the beginning as this implementation uses 1 based indexing
	fenwickTree := &FenwickTree{
		n:     len(array),
		array: append(newArray, array...),
		bit:   append(newArray, array...),
	}
	for i := 1; i < fenwickTree.n; i++ {
		nextPos := i + (i & -i)
		if nextPos <= fenwickTree.n {
			fenwickTree.bit[nextPos] += fenwickTree.bit[i]
		}
	}
	return fenwickTree
}

// PrefixSum returns the sum of the prefix ending at position pos.
func (f *FenwickTree) PrefixSum(pos int) int {