fenwick

package module
Version: v0.0.0-...-5f8823d Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 12, 2018 License: BSD-2-Clause Imports: 0 Imported by: 1

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.

package main

import (
	"fmt"

	"github.com/yourbasic/fenwick"
)

func main() {
	a := fenwick.New(1, 2, 3, 4, 5)
	fmt.Println(a.Sum(4))
}
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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL