fenwicktree

Documentation

Overview

Fenwick Tree Data Structure for efficient range queries on an array of integers. Also known as Binary Indexed Tree. It can query the sum of any range of the array and can update the array at a specific position by adding a value to it (point update). Build: O(N) Query: O(log(N)) Update: O(log(N)) reference: https://brilliant.org/wiki/fenwick-tree/

Index

• type FenwickTree
  • func NewFenwickTree(array []int) *FenwickTree
  • func (f *FenwickTree) Add(pos int, value int)
  • func (f *FenwickTree) PrefixSum(pos int) int
  • func (f *FenwickTree) RangeSum(l int, r int) int

Types

type FenwickTree

type FenwickTree struct {
	// contains filtered or unexported fields
}

FenwickTree represents the data structure of the Fenwick Tree

func NewFenwickTree

func NewFenwickTree(array []int) *FenwickTree

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.

func (*FenwickTree) Add

func (f *FenwickTree) Add(pos int, value int)

Add Adds value to the element at position pos of the array and recomputes the range sums.

func (*FenwickTree) PrefixSum

func (f *FenwickTree) PrefixSum(pos int) int

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

func (*FenwickTree) RangeSum

func (f *FenwickTree) RangeSum(l int, r int) int

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