bit

Documentation

Index

• type BIT
  • func NewBIT(size int) *BIT
  • func (this *BIT) Len() int
  • func (this *BIT) Query(index int) int
  • func (this *BIT) Update(index, val int)

Types

type BIT

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

func NewBIT

func NewBIT(size int) *BIT

NewBIT returns an object representing Binary Index Tree or Fenwick Tree of given size.

func (*BIT) Len

func (this *BIT) Len() int

Len returns the size of the BIT. Complexity - O(1).

func (*BIT) Query

func (this *BIT) Query(index int) int

Query returns a sum of first [0...index] elements of Binary Index Tree. Complexity - O(LogN).

func (*BIT) Update

func (this *BIT) Update(index, val int)

Update updates a node in Binary Index Tree (BIT) at given index in BIT. The given value `val` is added to BIT[i] and all of its ancestors in tree. Complexity - O(LogN).