fenwick

package module
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Jul 13, 2026 License: MIT Imports: 4 Imported by: 0

README

Fenwick Tree for Go

Build Tests codecov Go Reference Go Version GitHub Release GitHub issues GitHub stars

A zero-based, concurrency-safe Fenwick tree (Binary Indexed Tree) for Go.

The package supports three integration styles:

  1. Built-in signed numeric types through NewNumeric.
  2. Dependency injection through Operations[T] and NewWithOperations.
  3. Legacy self-describing models through the Value interface and New.

It also provides a sharded implementation for write-heavy concurrent workloads.

Installation

go get github.com/Sheryorov/fenwick

Core capabilities

  • O(n) construction
  • O(log n) point updates
  • O(log n) prefix and range queries
  • zero-based public indexes
  • inclusive ranges
  • concurrent-safe standard tree
  • sharded tree for parallel updates
  • fast and exact sharded query modes
  • injectable aggregation behavior for domain models

1. Numeric values

Use NewNumeric for signed integer and floating-point types.

package main

import (
    "fmt"

    "github.com/Sheryorov/fenwick"
)

func main() {
    tree := fenwick.NewNumeric([]int64{3, 2, 5, 1, 4})

    sum, err := tree.RangeSum(1, 3)
    if err != nil {
        panic(err)
    }

    fmt.Println(sum) // 8

    if err := tree.Set(2, 10); err != nil {
        panic(err)
    }

    fmt.Println(tree.Total()) // 20
}

Supported numeric families:

  • int, int8, int16, int32, int64
  • float32, float64
  • named types with one of those underlying types

Unsigned integers are intentionally excluded because Set may require a negative delta.

2. Injecting domain-model operations

Domain models do not need to import or implement anything from this package. Aggregation behavior is injected separately through Operations[T].

type Operations[T any] interface {
    Zero() T
    Add(a, b T) T
    Sub(a, b T) T
}

Example domain model:

package main

import (
    "fmt"

    "github.com/Sheryorov/fenwick"
)

type Metrics struct {
    Requests int64
    Duration float64
}

type MetricsOperations struct{}

func (MetricsOperations) Zero() Metrics {
    return Metrics{}
}

func (MetricsOperations) Add(a, b Metrics) Metrics {
    return Metrics{
        Requests: a.Requests + b.Requests,
        Duration: a.Duration + b.Duration,
    }
}

func (MetricsOperations) Sub(a, b Metrics) Metrics {
    return Metrics{
        Requests: a.Requests - b.Requests,
        Duration: a.Duration - b.Duration,
    }
}

func main() {
    tree := fenwick.NewWithOperations(
        []Metrics{
            {Requests: 10, Duration: 1.2},
            {Requests: 20, Duration: 2.8},
            {Requests: 15, Duration: 1.5},
        },
        MetricsOperations{},
    )

    result, err := tree.RangeSum(0, 1)
    if err != nil {
        panic(err)
    }

    fmt.Printf("requests=%d duration=%.1f\n", result.Requests, result.Duration)
    // requests=30 duration=4.0
}

This is the recommended integration style when domain models should remain independent from the Fenwick package.

Function-based injection

For small integrations, use OperationFuncs[T] instead of defining a named operations type.

ops := fenwick.OperationFuncs[int64]{
    ZeroFunc: func() int64 { return 0 },
    AddFunc:  func(a, b int64) int64 { return a + b },
    SubFunc:  func(a, b int64) int64 { return a - b },
}

tree := fenwick.NewWithOperations([]int64{1, 2, 3}, ops)

3. Legacy Value models

A model may implement Value directly:

type Value interface {
    Add(other Value) Value
    Sub(other Value) Value
    Zero() Value
}

Then it can be constructed with New:

tree := fenwick.New([]fenwick.Int64{1, 2, 3})

Built-in wrappers are provided:

  • fenwick.Int
  • fenwick.Int64
  • fenwick.Float32
  • fenwick.Float64
  • fenwick.Uint
  • fenwick.Uint64

For new domain code, injected Operations[T] is usually safer because it avoids runtime type assertions inside the model.

Standard tree API

type Tree[T any]
Method Description Complexity
NewNumeric(values) Build a numeric tree O(n)
NewWithOperations(values, ops) Build with injected behavior O(n)
New(values) Build from Value models O(n)
Len() Number of values O(1)
At(index) Read one value O(1)
Add(index, delta) Add a delta O(log n)
Set(index, value) Replace a value O(log n)
PrefixSum(index) Inclusive sum [0, index] O(log n)
RangeSum(left, right) Inclusive sum [left, right] O(log n)
Total() Sum all values O(log n)
Values() Return a copy O(n)

All exported methods are safe for concurrent use.

Indexing and ranges

The public API is zero-based.

values := []int64{3, 2, 5, 1, 4}

Valid indexes are 0 through 4.

Ranges are inclusive:

tree.RangeSum(1, 3)

returns 2 + 5 + 1.

Sharded tree

The sharded implementation divides values into independently locked contiguous trees.

Numeric constructors
tree := fenwick.NewNumericSharded(values)
tree := fenwick.NewNumericShardedWithCount(values, 32)
Injected-operations constructors
tree := fenwick.NewShardedWithOperations(values, ops)
tree := fenwick.NewShardedWithOperationsAndCount(values, 32, ops)
Legacy Value constructors
tree := fenwick.NewSharded(values)
tree := fenwick.NewShardedWithCount(values, 32)
Fast queries
  • PrefixSum
  • RangeSum
  • Total

Fast queries minimize lock duration. During concurrent writes across multiple shards, they are race-free but may combine values observed at slightly different moments.

Exact queries
  • ExactPrefixSum
  • ExactRangeSum
  • ExactTotal
  • Values

Exact queries lock all involved shards in deterministic order and return one consistent cross-shard snapshot.

Choosing an integration style

Use NewNumeric when:

  • values are signed numbers or floats;
  • direct arithmetic is sufficient;
  • maximum simplicity and performance are desired.

Use NewWithOperations when:

  • values are domain structs;
  • aggregation behavior should be injected;
  • models should not depend on this package;
  • compile-time type safety is important.

Use New with Value when:

  • existing models already implement the legacy interface;
  • backward compatibility is required.

Algebra requirements

Injected operations must obey:

  • associativity: Add(Add(a, b), c) == Add(a, Add(b, c))
  • identity: Add(a, Zero()) == a
  • inverse behavior: Sub(a, a) == Zero()

Breaking these rules produces incorrect prefix and range results.

Errors

fenwick.ErrIndexOutOfRange
fenwick.ErrInvalidRange

Use errors.Is:

value, err := tree.At(-1)
if errors.Is(err, fenwick.ErrIndexOutOfRange) {
    // handle invalid index
}

Concurrency

Tree[T] uses one sync.RWMutex.

ShardedTree[T] uses one sync.RWMutex per shard, allowing updates to different shards to proceed concurrently.

Sharding is not automatically faster. Benchmark with the expected read/write ratio and index distribution.

Limitations

  • arithmetic overflow is not detected;
  • floating-point accumulation follows IEEE-754 semantics;
  • injected operations are trusted to satisfy the documented algebraic laws;
  • OperationFuncs panics if a required function field is nil and used;
  • legacy Value implementations may panic on incompatible runtime type assertions;
  • fast sharded reads are not a single global snapshot during concurrent writes.

Development

go test ./...
go test -race ./...
go vet ./...
go test ./... -coverprofile=coverage.out
go tool cover -func=coverage.out
go test -run='^$' -bench=. -benchmem ./...

Repository

Reference

Peter M. Fenwick, A New Data Structure for Cumulative Frequency Tables, 1994.

Atomic batch mutations

Both Tree[T] and ShardedTree[T] support applying multiple point changes with one call:

err := tree.Apply(
    fenwick.AddMutation(0, int64(5)),
    fenwick.SetMutation(3, int64(20)),
    fenwick.AddMutation(3, int64(-2)),
)
if err != nil {
    // no mutation was applied when validation failed
}

Mutations are evaluated in the order supplied. This is relevant when several mutations target the same index.

Tree.Apply acquires its write lock once. Readers and writers observe either the state before the complete batch or the state after it.

ShardedTree.Apply validates the complete batch first, groups the affected indexes by shard, and locks only the touched shards in ascending order. Exact read methods observe the complete batch atomically. Fast cross-shard reads keep their documented non-snapshot semantics.

Available mutation helpers:

fenwick.AddMutation(index, delta)
fenwick.SetMutation(index, value)

An empty batch is a no-op. Invalid indexes or mutation kinds are rejected before any changes are made.

Documentation

Overview

Package fenwick implements concurrency-safe Fenwick trees (binary indexed trees) for point updates and prefix/range aggregation queries.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	ErrIndexOutOfRange = errors.New("fenwick: index out of range")
	ErrInvalidRange    = errors.New("fenwick: invalid range")
)

Functions

This section is empty.

Types

type Float32 

type Float32 float32

Float32 is a Value wrapper for float32 that implements arithmetic operations.

func (Float32) Add 

func (f Float32) Add(other Value) Value

func (Float32) Sub 

func (f Float32) Sub(other Value) Value

func (Float32) Zero 

func (f Float32) Zero() Value

type Float64 

type Float64 float64

Float64 is a Value wrapper for float64 that implements arithmetic operations.

func (Float64) Add 

func (f Float64) Add(other Value) Value

func (Float64) Sub 

func (f Float64) Sub(other Value) Value

func (Float64) Zero 

func (f Float64) Zero() Value

type Int 

type Int int

Int is a Value wrapper for int that implements arithmetic operations.

func (Int) Add 

func (i Int) Add(other Value) Value

func (Int) Sub 

func (i Int) Sub(other Value) Value

func (Int) Zero 

func (i Int) Zero() Value

type Int64 

type Int64 int64

Int64 is a Value wrapper for int64 that implements arithmetic operations.

func (Int64) Add 

func (i Int64) Add(other Value) Value

func (Int64) Sub 

func (i Int64) Sub(other Value) Value

func (Int64) Zero 

func (i Int64) Zero() Value

type Mutation 

type Mutation[T any] struct {
	Index int
	Kind  MutationKind
	Value T
}

Mutation describes one point change applied by Apply.

Mutations are evaluated in slice order. This matters when multiple mutations target the same index.

func AddMutation 

func AddMutation[T any](index int, delta T) Mutation[T]

AddMutation creates an additive point mutation.

func SetMutation 

func SetMutation[T any](index int, value T) Mutation[T]

SetMutation creates a replacement point mutation.

type MutationKind 

type MutationKind uint8

MutationKind identifies how a batch mutation changes a value. 

const (
	// MutationAdd increments the current value by Mutation.Value.
	MutationAdd MutationKind = iota + 1
	// MutationSet replaces the current value with Mutation.Value.
	MutationSet
)

type Number 

type Number interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~float32 | ~float64
}

Number contains the built-in signed integer and floating-point families. Unsigned types are deliberately excluded because Set may require a negative delta when replacing a larger value with a smaller one.

type NumericOperations 

type NumericOperations[T Number] struct{}

NumericOperations implements Operations for signed numeric types.

func (NumericOperations[T]) Add 

func (NumericOperations[T]) Add(a, b T) T

func (NumericOperations[T]) Sub 

func (NumericOperations[T]) Sub(a, b T) T

func (NumericOperations[T]) Zero 

func (NumericOperations[T]) Zero() T

type OperationFuncs 

type OperationFuncs[T any] struct {
	ZeroFunc func() T
	AddFunc  func(a, b T) T
	SubFunc  func(a, b T) T
}

OperationFuncs adapts functions to Operations. It is convenient when the aggregation behavior is local to the caller and does not warrant a named operations type.

func (OperationFuncs[T]) Add 

func (f OperationFuncs[T]) Add(a, b T) T

func (OperationFuncs[T]) Sub 

func (f OperationFuncs[T]) Sub(a, b T) T

func (OperationFuncs[T]) Zero 

func (f OperationFuncs[T]) Zero() T

type Operations 

type Operations[T any] interface {
	Zero() T
	Add(a, b T) T
	Sub(a, b T) T
}

Operations defines the additive algebra used by a Fenwick tree.

It is intentionally separate from the stored model type. This allows domain models to remain free of Fenwick-specific methods and lets callers inject aggregation behavior at construction time.

Implementations must provide an additive identity and satisfy the usual additive group laws required by range sums: Add must be associative, Zero must be an identity, and Sub must undo Add.

type ShardedTree 

type ShardedTree[T any] struct {
	// contains filtered or unexported fields
}

ShardedTree splits values into independently locked contiguous Fenwick trees.

func NewNumericSharded 

func NewNumericSharded[T Number](values []T) *ShardedTree[T]

NewNumericSharded constructs a sharded tree for signed numeric values.

func NewNumericShardedWithCount 

func NewNumericShardedWithCount[T Number](values []T, shardCount int) *ShardedTree[T]

NewNumericShardedWithCount constructs a numeric sharded tree with an explicit shard count.

func NewSharded 

func NewSharded[T Value](values []T) *ShardedTree[T]

NewSharded constructs a sharded tree for Value models.

func NewShardedWithCount 

func NewShardedWithCount[T Value](values []T, shardCount int) *ShardedTree[T]

NewShardedWithCount constructs a sharded tree for Value models with an explicit shard count.

func NewShardedWithOperations 

func NewShardedWithOperations[T any](values []T, ops Operations[T]) *ShardedTree[T]

NewShardedWithOperations chooses the shard count from GOMAXPROCS.

func NewShardedWithOperationsAndCount 

func NewShardedWithOperationsAndCount[T any](values []T, shardCount int, ops Operations[T]) *ShardedTree[T]

NewShardedWithOperationsAndCount injects aggregation behavior and uses an explicit shard count.

func (*ShardedTree[T]) Add 

func (t *ShardedTree[T]) Add(index int, delta T) error

func (*ShardedTree[T]) Apply 

func (t *ShardedTree[T]) Apply(mutations ...Mutation[T]) error

Apply atomically applies a batch of point mutations in slice order.

All mutations are validated before locks are acquired. Every touched shard is then write-locked in ascending order, preventing deadlocks and ensuring exact readers observe either the state before the whole batch or the state after it. Fast cross-shard readers retain their documented non-snapshot semantics. An empty batch is a no-op.

func (*ShardedTree[T]) At 

func (t *ShardedTree[T]) At(index int) (T, error)

func (*ShardedTree[T]) ExactPrefixSum 

func (t *ShardedTree[T]) ExactPrefixSum(index int) (T, error)

func (*ShardedTree[T]) ExactRangeSum 

func (t *ShardedTree[T]) ExactRangeSum(left, right int) (T, error)

func (*ShardedTree[T]) ExactTotal 

func (t *ShardedTree[T]) ExactTotal() T

func (*ShardedTree[T]) Len 

func (t *ShardedTree[T]) Len() int

func (*ShardedTree[T]) PrefixSum 

func (t *ShardedTree[T]) PrefixSum(index int) (T, error)

func (*ShardedTree[T]) RangeSum 

func (t *ShardedTree[T]) RangeSum(left, right int) (T, error)

func (*ShardedTree[T]) Set 

func (t *ShardedTree[T]) Set(index int, value T) error

func (*ShardedTree[T]) ShardCount 

func (t *ShardedTree[T]) ShardCount() int

func (*ShardedTree[T]) Total 

func (t *ShardedTree[T]) Total() T

func (*ShardedTree[T]) Values 

func (t *ShardedTree[T]) Values() []T

type Tree 

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree stores values aggregated by injected Operations. Public indexes are zero-based; internal Fenwick indexes are one-based.

Example 
package main

import (
	"fmt"

	"github.com/Sheryorov/fenwick"
)

func main() {
	ft := fenwick.NewNumeric[int64]([]int64{3, 2, 5, 1, 4})

	sum, _ := ft.RangeSum(1, 3)
	fmt.Println(sum)

	_ = ft.Set(2, 10)
	sum, _ = ft.RangeSum(1, 3)
	fmt.Println(sum)

}

Output:
8
13

func New 

func New[T Value](values []T) *Tree[T]

New constructs a tree for models implementing Value.

func NewNumeric 

func NewNumeric[T Number](values []T) *Tree[T]

NewNumeric constructs a tree for signed integers or floating-point values.

func NewWithOperations 

func NewWithOperations[T any](values []T, ops Operations[T]) *Tree[T]

NewWithOperations constructs a tree using caller-provided aggregation behavior. The input slice is copied and construction takes O(n).

func (*Tree[T]) Add 

func (t *Tree[T]) Add(index int, delta T) error

func (*Tree[T]) Apply 

func (t *Tree[T]) Apply(mutations ...Mutation[T]) error

Apply atomically applies a batch of point mutations in slice order.

All mutations are validated before any value is changed. The tree lock is acquired once, so readers and writers observe either the state before the whole batch or the state after it. An empty batch is a no-op.

func (*Tree[T]) At 

func (t *Tree[T]) At(index int) (T, error)

func (*Tree[T]) Len 

func (t *Tree[T]) Len() int

func (*Tree[T]) PrefixSum 

func (t *Tree[T]) PrefixSum(index int) (T, error)

func (*Tree[T]) RangeSum 

func (t *Tree[T]) RangeSum(left, right int) (T, error)

func (*Tree[T]) Set 

func (t *Tree[T]) Set(index int, value T) error

func (*Tree[T]) Total 

func (t *Tree[T]) Total() T

func (*Tree[T]) Values 

func (t *Tree[T]) Values() []T

type Uint 

type Uint uint

Uint is a Value wrapper for uint that implements arithmetic operations.

func (Uint) Add 

func (u Uint) Add(other Value) Value

func (Uint) Sub 

func (u Uint) Sub(other Value) Value

func (Uint) Zero 

func (u Uint) Zero() Value

type Uint64 

type Uint64 uint64

Uint64 is a Value wrapper for uint64 that implements arithmetic operations.

func (Uint64) Add 

func (u Uint64) Add(other Value) Value

func (Uint64) Sub 

func (u Uint64) Sub(other Value) Value

func (Uint64) Zero 

func (u Uint64) Zero() Value

type Value 

type Value interface {
	Add(other Value) Value
	Sub(other Value) Value
	Zero() Value
}

Value is the legacy self-describing model interface. Types implementing it can be passed to New and NewSharded directly. New code that should keep domain models independent from this package can use NewWithOperations and inject an Operations implementation instead.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.