README

Your basic Fenwick tree GoDoc

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.

Checklist

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.

Roadmap

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
      

      Index

      Examples

      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 (*List) Add

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

            Add adds n to the element at index i.

            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.

                        Source Files