package corpus

type fenwikTree struct {
	array   []int64
	data    []int64
	fullSum int64

	size     int
	capacity int
}

func (t *fenwikTree) addNew(val int64) {
	if t.size+1 >= t.capacity {
		t.extendAndRebuild()
	}

	t.size++
	t.add(t.size, val)
}

func (t *fenwikTree) add(ind int, val int64) {
	t.fullSum += val
	t.array[ind] += val
	for ind < t.capacity {
		t.data[ind] += val
		ind += ind & -ind
	}
}

func (t *fenwikTree) get(ind int) int64 {
	return t.array[ind]
}

func (t *fenwikTree) set(ind int, val int64) {
	t.add(ind, val-t.get(ind))
}

func (t *fenwikTree) prefixSumTo(ind int) (sum int64) {
	for ind > 0 {
		sum += t.data[ind]
		ind -= ind & -ind
	}
	return
}

func (t *fenwikTree) extendAndRebuild() {
	if t.capacity == 0 {
		t.capacity = 16
	} else {
		t.capacity *= 2
	}

	oldArray := t.array
	t.array = make([]int64, t.capacity)
	t.data = make([]int64, t.capacity)
	t.fullSum = 0

	for i := 1; i < len(oldArray); i++ {
		t.add(i, oldArray[i])
	}
}