Method PrefixSum

structure/fenwicktree/fenwicktree.go:37–46

PrefixSum returns the sum of the prefix ending at position pos.

(pos int)

// PrefixSum returns the sum of the prefix ending at position pos.
func (f *FenwickTree) PrefixSum(pos int) int {
	if pos > f.n {
		return 0
	}
	prefixSum := 0
	for i := pos; i > 0; i -= (i & -i) {
		prefixSum += f.bit[i]
	}
	return prefixSum
}

// RangeSum returns the sum of the elements in the range l to r
// both inclusive.