README
¶
segmenttree
Generic segment trees for Go: point updates, lazy range updates, boundary
searches, and sparse int64 coordinate spaces.
go get github.com/satya-sudo/segmenttree
The package uses Go-style half-open ranges: [left, right).
Standard tree
Callers provide an identity value and an associative combine function:
tree := segmenttree.New(
[]int{2, 1, 3, 4, 5},
0,
segmenttree.Sum[int],
)
sum := tree.Query(1, 4) // 1 + 3 + 4 = 8
tree.Set(2, 10)
sum = tree.Query(1, 4) // 1 + 10 + 4 = 15
Tree also supports At, All, Len, and two logarithmic boundary
searches:
// Largest right for which the sum of [0, right) is at most 12.
right := tree.MaxRight(0, func(sum int) bool {
return sum <= 12
})
// Smallest left for which the sum of [left, tree.Len()) is at most 9.
left := tree.MinLeft(tree.Len(), func(sum int) bool {
return sum <= 9
})
Boundary-search predicates must be monotone and must return true for the
identity value.
Lazy tree
LazyTree[T, U] stores aggregates of type T and applies range updates of
type U. The types can differ.
This range-add/range-sum tree uses int for both:
tree := segmenttree.NewLazy(
[]int{1, 2, 3, 4, 5},
0, // aggregate identity
segmenttree.Sum[int], // combine adjacent aggregates
0, // update identity
func(add, sum, length int) int {
return sum + add*length
},
segmenttree.Sum[int], // compose additions
)
tree.RangeApply(1, 4, 10)
sum := tree.Query(0, 5) // 45
Custom update types can represent assignment, affine transformations, bit toggles, or application-specific actions. Update composition has an explicit order:
compose(newer, older)
The result must be equivalent to applying older first and newer second.
LazyTree also provides Set, At, All, Len, MaxRight, and MinLeft.
Dynamic tree
DynamicTree is an implicit tree for sparse values in a very large coordinate
space. It allocates only paths touched by Set.
tree := segmenttree.NewDynamic(
int64(-1_000_000_000_000),
int64(1_000_000_000_000),
0,
segmenttree.Sum[int],
)
tree.Set(-50_000_000_000, 4)
tree.Set(700_000_000_000, 9)
sum := tree.Query(-100_000_000_000, 0) // 4
nodes := tree.Allocated()
Coordinates and query bounds are int64. Missing coordinates hold the
identity value. The implementation uses an overflow-safe midpoint and can
span ranges crossing math.MinInt64 and math.MaxInt64.
DynamicTree also supports At, All, Bounds, Allocated, MaxRight,
and MinLeft.
Reusable operations
The package includes generic combine functions:
| Function | Typical identity |
|---|---|
Sum |
0 |
Product |
1 |
Min |
largest value for the numeric type |
Max |
smallest value for the numeric type |
BitwiseAnd |
value with every bit set |
BitwiseOr |
0 |
BitwiseXor |
0 |
For example:
maximums := segmenttree.New(values, math.MinInt, segmenttree.Max[int])
products := segmenttree.New(values, 1, segmenttree.Product[int])
User-defined numeric types with supported underlying types also work.
Algebraic requirements
Every tree relies on an associative combine function and a two-sided identity:
combine(combine(a, b), c) == combine(a, combine(b, c))
combine(identity, value) == value
combine(value, identity) == value
Combine does not need to be commutative. Queries and boundary searches preserve left-to-right order.
Lazy updates must additionally distribute over combined segments:
apply(u, combine(a, b), lenA + lenB)
==
combine(apply(u, a, lenA), apply(u, b, lenB))
Complexity
| Type and operation | Time | Space |
|---|---|---|
New / NewLazy |
O(n) | O(n) |
Tree.At / Tree.All |
O(1) | O(1) |
Tree.Set / Tree.Query |
O(log n) | O(1) |
Tree.MaxRight / Tree.MinLeft |
O(log n) | O(1) |
LazyTree.Set / At / RangeApply / Query |
O(log n) | O(log n) call stack |
LazyTree.MaxRight / MinLeft |
O(log n) | O(log n) call stack |
DynamicTree.Set / At / Query |
O(log coordinate span) | allocated on demand |
DynamicTree.MaxRight / MinLeft |
O(log coordinate span) | O(log coordinate span) call stack |
Trees panic for invalid indexes and ranges, consistent with ordinary Go slice indexing. The data structures are not safe for concurrent mutation.
License
MIT
Documentation
¶
Overview ¶
Package segmenttree provides generic segment trees for efficient point updates, lazy range updates, boundary searches, and sparse coordinate spaces.
A Tree is parameterized by an associative combine function and its identity value. Commutativity is not required, so operations such as string concatenation work as expected.
Tree is the compact point-update implementation. LazyTree supports composable range updates, and DynamicTree allocates nodes on demand over an int64 coordinate range.
All ranges are half-open, matching Go slices: Query(2, 5) combines the values at indexes 2, 3, and 4.
Index ¶
- func BitwiseAnd[T Integer](left, right T) T
- func BitwiseOr[T Integer](left, right T) T
- func BitwiseXor[T Integer](left, right T) T
- func Max[T Number](left, right T) T
- func Min[T Number](left, right T) T
- func Product[T Number](left, right T) T
- func Sum[T Number](left, right T) T
- type ApplyFunc
- type CombineFunc
- type ComposeFunc
- type DynamicTree
- func (t *DynamicTree[T]) All() T
- func (t *DynamicTree[T]) Allocated() int
- func (t *DynamicTree[T]) At(index int64) T
- func (t *DynamicTree[T]) Bounds() (lower, upper int64)
- func (t *DynamicTree[T]) MaxRight(left int64, predicate func(T) bool) int64
- func (t *DynamicTree[T]) MinLeft(right int64, predicate func(T) bool) int64
- func (t *DynamicTree[T]) Query(left, right int64) T
- func (t *DynamicTree[T]) Set(index int64, value T)
- type Float
- type Integer
- type LazyTree
- func (t *LazyTree[T, U]) All() T
- func (t *LazyTree[T, U]) At(i int) T
- func (t *LazyTree[T, U]) Len() int
- func (t *LazyTree[T, U]) MaxRight(left int, predicate func(T) bool) int
- func (t *LazyTree[T, U]) MinLeft(right int, predicate func(T) bool) int
- func (t *LazyTree[T, U]) Query(left, right int) T
- func (t *LazyTree[T, U]) RangeApply(left, right int, update U)
- func (t *LazyTree[T, U]) Set(i int, value T)
- type Number
- type Tree
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BitwiseOr ¶
func BitwiseOr[T Integer](left, right T) T
BitwiseOr returns left | right. The identity value is zero.
func BitwiseXor ¶
func BitwiseXor[T Integer](left, right T) T
BitwiseXor returns left ^ right. The identity value is zero.
func Max ¶
func Max[T Number](left, right T) T
Max returns the larger value.
Callers must supply a suitable minimum value as the tree identity. For floating-point trees, callers are responsible for choosing the desired NaN behavior.
func Min ¶
func Min[T Number](left, right T) T
Min returns the smaller value.
Callers must supply a suitable maximum value as the tree identity. For floating-point trees, callers are responsible for choosing the desired NaN behavior.
Types ¶
type ApplyFunc ¶
ApplyFunc applies an update to the aggregate of a segment containing length elements.
Applying an update to a combined segment must produce the same result as applying it separately to both child segments and then combining them.
type CombineFunc ¶
type CombineFunc[T any] func(left, right T) T
CombineFunc combines two adjacent segments.
CombineFunc must be associative:
combine(combine(a, b), c) == combine(a, combine(b, c))
The order of the arguments is significant; combine need not be commutative.
type ComposeFunc ¶
type ComposeFunc[U any] func(newer, older U) U
ComposeFunc combines two updates. ComposeFunc(newer, older) must return an update equivalent to applying older first and newer second.
type DynamicTree ¶
type DynamicTree[T any] struct { // contains filtered or unexported fields }
DynamicTree is an implicit segment tree over an int64 coordinate range.
Nodes are allocated only along paths touched by Set, making DynamicTree suitable for sparse data in very large coordinate spaces. Unset coordinates have the identity value.
DynamicTree is not safe for concurrent mutation.
Example ¶
package main
import (
"fmt"
"github.com/satya-sudo/segmenttree"
)
func main() {
tree := segmenttree.NewDynamic(int64(-1_000_000_000), int64(1_000_000_000), 0, segmenttree.Sum[int])
tree.Set(-50_000_000, 4)
tree.Set(700_000_000, 9)
fmt.Println(tree.Query(-100_000_000, 0))
fmt.Println(tree.All())
}
Output: 4 13
func NewDynamic ¶
func NewDynamic[T any]( lower, upper int64, identity T, combine CombineFunc[T], ) *DynamicTree[T]
NewDynamic returns an empty DynamicTree covering [lower, upper).
NewDynamic panics if lower >= upper or combine is nil.
func (*DynamicTree[T]) All ¶
func (t *DynamicTree[T]) All() T
All combines every value in the tree in O(1).
func (*DynamicTree[T]) Allocated ¶
func (t *DynamicTree[T]) Allocated() int
Allocated returns the number of currently allocated internal and leaf nodes.
func (*DynamicTree[T]) At ¶
func (t *DynamicTree[T]) At(index int64) T
At returns the value at coordinate index in O(log(upper-lower)). Unset coordinates return the identity value.
At panics if index is outside the tree bounds.
func (*DynamicTree[T]) Bounds ¶
func (t *DynamicTree[T]) Bounds() (lower, upper int64)
Bounds returns the half-open coordinate range [lower, upper).
func (*DynamicTree[T]) MaxRight ¶
func (t *DynamicTree[T]) MaxRight(left int64, predicate func(T) bool) int64
MaxRight returns the largest right in [left, upper] for which predicate(Query(left, right)) is true.
predicate has the same requirements as Tree.MaxRight. The operation runs in O(log(upper-lower)) for a monotone predicate.
func (*DynamicTree[T]) MinLeft ¶
func (t *DynamicTree[T]) MinLeft(right int64, predicate func(T) bool) int64
MinLeft returns the smallest left in [lower, right] for which predicate(Query(left, right)) is true.
predicate has the same requirements as Tree.MinLeft. The operation runs in O(log(upper-lower)) for a monotone predicate.
func (*DynamicTree[T]) Query ¶
func (t *DynamicTree[T]) Query(left, right int64) T
Query combines values in [left, right) in O(log(upper-lower)). Query(left, left) returns the identity value.
Query panics unless lower <= left <= right <= upper.
func (*DynamicTree[T]) Set ¶
func (t *DynamicTree[T]) Set(index int64, value T)
Set replaces the value at coordinate index in O(log(upper-lower)). It allocates nodes along the coordinate's path as needed.
Set panics if index is outside the tree bounds.
type Float ¶
Float is the set of built-in floating-point types and user-defined types whose underlying type is a floating-point number.
type Integer ¶
type Integer interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}
Integer is the set of built-in integer types and user-defined types whose underlying type is an integer.
type LazyTree ¶
type LazyTree[T, U any] struct { // contains filtered or unexported fields }
LazyTree supports range updates and range queries in O(log n).
T is the aggregate type and U is the update type. They need not be the same. LazyTree is not safe for concurrent access because even read-like operations may push pending updates into child nodes.
Example ¶
package main
import (
"fmt"
"github.com/satya-sudo/segmenttree"
)
func newRangeAddSumTree(values []int) *segmenttree.LazyTree[int, int] {
return segmenttree.NewLazy(
values,
0,
segmenttree.Sum[int],
0,
func(update, aggregate, length int) int {
return aggregate + update*length
},
segmenttree.Sum[int],
)
}
func main() {
tree := newRangeAddSumTree([]int{1, 2, 3, 4})
tree.RangeApply(1, 4, 5)
fmt.Println(tree.Query(0, 3))
fmt.Println(tree.At(3))
}
Output: 16 9
func NewLazy ¶
func NewLazy[T, U any]( values []T, identity T, combine CombineFunc[T], updateIdentity U, apply ApplyFunc[T, U], compose ComposeFunc[U], ) *LazyTree[T, U]
NewLazy builds a LazyTree from values in O(n).
identity and combine follow the same monoid rules as New. updateIdentity must represent an update that changes nothing. NewLazy panics if combine, apply, or compose is nil.
func NewLazySize ¶
func NewLazySize[T, U any]( n int, identity T, combine CombineFunc[T], updateIdentity U, apply ApplyFunc[T, U], compose ComposeFunc[U], ) *LazyTree[T, U]
NewLazySize returns a LazyTree of length n whose values are initialized to identity. It panics if n is negative or any function is nil.
func (*LazyTree[T, U]) All ¶
func (t *LazyTree[T, U]) All() T
All combines every element in O(1). It returns the identity value when the tree is empty.
func (*LazyTree[T, U]) At ¶
At returns the current value at index i in O(log n). It panics if i is outside [0, Len()).
func (*LazyTree[T, U]) MaxRight ¶
MaxRight is the lazy-tree equivalent of Tree.MaxRight and runs in O(log n).
func (*LazyTree[T, U]) MinLeft ¶
MinLeft is the lazy-tree equivalent of Tree.MinLeft and runs in O(log n).
func (*LazyTree[T, U]) Query ¶
Query combines the elements in [left, right) in O(log n). Query(left, left) returns the identity value.
Query panics unless 0 <= left <= right <= Len().
func (*LazyTree[T, U]) RangeApply ¶
RangeApply applies update to every element in [left, right) in O(log n). Applying an update to an empty range has no effect.
RangeApply panics unless 0 <= left <= right <= Len().
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree supports point updates and half-open range queries in O(log n).
Tree is not safe for concurrent mutation. A caller may protect it with a mutex when it is shared between goroutines.
Example ¶
package main
import (
"fmt"
"github.com/satya-sudo/segmenttree"
)
func main() {
max := func(a, b int) int {
if a > b {
return a
}
return b
}
tree := segmenttree.New([]int{4, 1, 7, 3, 2}, -1, max)
fmt.Println(tree.Query(1, 4))
tree.Set(2, 0)
fmt.Println(tree.Query(1, 4))
}
Output: 7 3
func New ¶
func New[T any](values []T, identity T, combine CombineFunc[T]) *Tree[T]
New builds a Tree from values in O(n).
identity must be a two-sided identity for combine:
combine(identity, value) == value combine(value, identity) == value
New panics if combine is nil.
func NewSize ¶
func NewSize[T any](n int, identity T, combine CombineFunc[T]) *Tree[T]
NewSize returns a Tree of length n whose elements are initialized to identity. NewSize panics if n is negative or combine is nil.
func (*Tree[T]) All ¶
func (t *Tree[T]) All() T
All combines every element in the tree in O(1). It returns the identity value when the tree is empty.
func (*Tree[T]) MaxRight ¶
MaxRight returns the largest right in [left, Len()] for which predicate(Query(left, right)) is true.
predicate must be monotone: once it becomes false as right grows, it must remain false. It must also return true for the identity value. MaxRight runs in O(log n) and preserves the order of non-commutative combine functions.
MaxRight panics if left is outside [0, Len()], predicate is nil, or predicate(identity) is false.
func (*Tree[T]) MinLeft ¶
MinLeft returns the smallest left in [0, right] for which predicate(Query(left, right)) is true.
predicate must be monotone: once it becomes false as left moves left, it must remain false. It must also return true for the identity value. MinLeft runs in O(log n) and preserves the order of non-commutative combine functions.
MinLeft panics if right is outside [0, Len()], predicate is nil, or predicate(identity) is false.
Source Files