## README ¶

### Your basic Fenwick tree ##### Go 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. ##### Installation

Once you have installed Go, run this command to install the `fenwick` package:

``````go get github.com/yourbasic/fenwick
``````
##### Documentation

There is an online reference for the package at godoc.org/github.com/yourbasic/fenwick.

The only accepted reason to modify the API of this package is to handle issues that can't be resolved in any other reasonable way.

Stefan Nilsson – korthaj

## Documentation ¶

### Overview ¶

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.

Example

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

```Output:

10
```

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type List ¶

```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 ¶

`func New(n ...int64) *List`

New creates a new list with the given elements.

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

#### func (*List) Append ¶

`func (l *List) Append(n int64)`

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

#### func (*List) Get ¶

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

Get returns the element at index i.

#### func (*List) Len ¶

`func (l *List) Len() int`

Len returns the number of elements in the list.

#### func (*List) Set ¶

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

Set sets the element at index i to n.

#### func (*List) Sum ¶

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

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

#### func (*List) SumRange ¶

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

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