1 files changed, 61 insertions, 0 deletions
diff --git a/pkg/corpus/fenwik.go b/pkg/corpus/fenwik.go
new file mode 100644
index 000000000..3a49219ac
--- /dev/null
+++ b/pkg/corpus/fenwik.go
@@ -0,0 +1,61 @@
+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])
+	}
+}