fenwick: github.com/yourbasic/fenwick Index | Examples | Files

package fenwick

import "github.com/yourbasic/fenwick"

Package fenwick provides a list data structure supporting prefix sums.

A Fenwick tree, or binary indexed tree, is a space-efficient list data structure that can efficiently update elements and calculate prefix sums in a list of numbers.

Compared to a common array, a Fenwick tree achieves better balance between element update and prefix sum calculation – both operations run in O(log n) time – while using the same amount of memory. This is achieved by representing the list as an implicit tree, where the value of each node is the sum of the numbers in that subtree.

Compute the sum of the first 4 elements in a list.

Code:

a := fenwick.New(1, 2, 3, 4, 5)
fmt.Println(a.Sum(4))

Output:

10

Index

Examples

Package Files

list.go

type List Uses

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

List represents a list of numbers with support for efficient prefix sum computation. The zero value is an empty list.

func New Uses

func New(n ...int64) *List

New creates a new list with the given elements.

func (*List) Add Uses

func (l *List) Add(i int, n int64)

Add adds n to the element at index i.

func (*List) Append Uses

func (l *List) Append(n int64)

Append appends a new element to the end of the list.

func (*List) Get Uses

func (l *List) Get(i int) int64

Get returns the element at index i.

func (*List) Len Uses

func (l *List) Len() int

Len returns the number of elements in the list.

func (*List) Set Uses

func (l *List) Set(i int, n int64)

Set sets the element at index i to n.

func (*List) Sum Uses

func (l *List) Sum(i int) int64

Sum returns the sum of the elements from index 0 to index i-1.

func (*List) SumRange Uses

func (l *List) SumRange(i, j int) int64

SumRange returns the sum of the elements from index i to index j-1.

Updated 2018-07-27. Refresh now. Tools for package owners.