README
¶
Binary Indexed Tree
A Binary Indexed Tree (BIT), also known as Fenwick tree, is a data structure that can efficiently update elements and calculate the sum of a range of consecutive elements. It was originally proposed by Boris Ryabko [1] in 1989 and Peter Fenwick [2] in 1994.
If we query the sum of a range of consecutive numbers in an array, it takes O(n) time on average, by adding up the numbers. Alternatively, we can utilize a second array to save the prefix sums, hence the query can be done in O(1) time, but updating the elements becomes an O(n) operation. Therefore, a Fenwick tree is preferred when elements mutate frequently.
A Fenwick tree is a simple data structure to solve this problem. Construction takes O(n) time, but a BIT balances both the sum query and element update operations, performing no worse than O(log n) time.
Features
This library provides a pure go implementation with an extensive API. Updates and queries are supported on both numbers and prefix sums. They can be performed on a single element, a range of elements or the whole tree. There is no need to keep hold of the numbers array once the BIT is constructed, as the numbers can be calculated from the BIT. If required, the Fenwick tree can re-use the numbers array, avoiding memory allocations during BIT construction.
The construction of a Fenwick tree is most efficient when the number of elements is known at construction, using From(numbers). When only the number of elements is known at construction, the tree can be built using New(n) and numbers can be added through Set() and/or Add(). When the number of elements is unknown, the tree can be constructed with New() and numbers can be appended to the tree with Append().
This repository uses zero-based indexing. While this slightly complicates the implementation, it makes the Fenwick tree more natural to use.
The implementation is fast. The code is mostly allocation-free, loops are free from bounds checks, and the algorithms are optimized without adding too much complexity.
Installation
Install bit with go get:
$ go get -u github.com/gevg/bit
Usage
Construct the tree, initializing it with a number array, and iterate the prefix sums.
// initialize a number array, construct the BIT tree and iterate the prefix sums
numbers := []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
tree := From(numbers)
for i := range numbers {
fmt.Printf("tree(%d) = %d\n", i, tree.Sum(i))
}
Alternatively, one can construct a tree of a given length and subsequently add numbers.
Add() increases the value of a number at a given index, while Set() overwrites the existing value.
// Construct a tree of length 10, and add/set elements in various ways.
tree := New(10)
tree.Add(0, 1); tree.Set(1, 3); tree.Set(2, 5)
tree.RangeAdd(3, []int32{7, 9, 11}); tree.RangeSet(6, []int32{13, 15, 17, 19})
// Calculate the range sum for range [2, 4).
sums := tree.RangeSum(2, 4)
A third option is to create an empty tree and extend it with the Append function. One can append a single number or a range of numbers.
// Construct a tree of zero length.
tree := New()
// Append element 1 at index 0, followed by a range of 4 numbers.
tree = Append(tree, 1); tree = Append(tree, []int32{3, 5, 7, 9}...); tree = Append(tree, 11, 13)
Numbers and number ranges can be multiplied by a factor and the impact on the prefix sums can be shown.
// Scale all numbers in the tree with a factor 5.
tree.Scale(5)
// Scale the numbers in range [2, 8) with 6, and multiply the value at index 5 with -2.
tree.RangeScale(2, 8, 6); tree.Mul(5, -2)
// Each number in a range can also be multiplied with a different factor. RangeMul
// multiplies a range of 3 numbers with different factors, starting at index 2.
tree.RangeMul(2, []int32{2, 4, 6})
// Finally, the prefix sums are calculated and shown together with the numbers.
nums, sums := make([]int32, 6), make([]int32, 6)
nn := tree.Numbers(nums); ns := tree.Sums(sums)
fmt.Printf("numbers: %v, prefix sums: %v\n", nums, sums)
Similar operations exist for addition.
// Increase all numbers by 5, and add 6 to all numbers in the range [2, 8).
tree.Shift(5)
tree.RangeShift(2, 8, 6)
// Subsequently, subtract 2 from the number at index 5.
tree.Add(5, -2)
//Add to the range of length 3, starting at index 2, the values 2, 4, and 6, respectively
tree.RangeAdd(2, []int32{2, 4, 6})
// Copy the range of prefix sums, starting at index 2, in the sums slice and show.
sums := make([]int32, 4)
n := tree.RangeSum(2, sums)
fmt.Printf("%d prefix sums: %v\n", n, sums)
We can search the largest prefix sum, smaller than or equal to a given value. The algorithm only works for monotonically increasing prefix sums, as this is the prevalent use case. Other cases can be added when requested (through the issue tracker).
// Search the largest prefix sum, smaller than or equal to 6, and print out the index and value.
fmt.Printf("(i, sum) = (%d, %d)\n", tree.SearchSum(6))
To Do
Implementation of the following features:
- Add examples to documentation.
- Introduction of parameterized types as soon as they become available in the
golanguage. - 2D Fenwick tree?
- Cache-related performance improvements for large arrays at the cost of zero allocation BIT construction?
- An alternative implementation of some features in assemby using AVX2 SIMD?
License
bit is available under the BSD 3-Clause License.
References
Documentation
¶
Overview ¶
Package bit implements a Binary Indexed Tree.
Index ¶
- func Copy(dst, src Tree) int
- func Len(t Tree) int
- type Tree
- func (t Tree) Add(i int, value int32)
- func (t Tree) Mul(i int, value int32) int32
- func (t Tree) Number(i int) int32
- func (t Tree) Numbers(numbers []int32) int
- func (t Tree) RangeAdd(i int, numbers []int32)
- func (t Tree) RangeMul(i int, factors []int32)
- func (t Tree) RangeNumbers(lo int, buf []int32) int
- func (t Tree) RangeScale(lo, hi int, multiplier int32)
- func (t Tree) RangeSet(i int, numbers []int32)
- func (t Tree) RangeShift(lo, hi int, value int32)
- func (t Tree) RangeSum(lo, hi int) int32
- func (t *Tree) Reset()
- func (t Tree) Scale(value int32)
- func (t Tree) SearchSum(value int32) (int, int32)
- func (t Tree) Set(i int, number int32)
- func (t Tree) Shift(value int32)
- func (t Tree) Sum(i int) int32
- func (t Tree) Sums(sums []int32) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Tree ¶
type Tree []int32
Tree represents a Binary Indexed Tree (BIT) type.
func From ¶
From creates a Binary Indexed Tree from a slice of numbers. When the reUse option is set, the tree will use the numbers slice as its backing store, avoiding new allocations. Default behavior for the tree is to allocate its own backing store.
func New ¶
New creates a Binary Indexed Tree of n elements. If n is not provided, the tree length defaults to zero.
func (Tree) Add ¶
Add adds the given vanlue to the number in the tree at index i. If the index is outside of the tree boundaries, no value is added.
func (Tree) Mul ¶
Mul multiplies the number at index i with the given value. If the index is outside of the tree boundaries, no modifications are done.
func (Tree) Number ¶
Number returns the element at index i. If i is outside of the tree, 0 will be returned.
func (Tree) Numbers ¶
Numbers returns all numbers in the tree. The caller provides the array to store the numbers. If the numbers slice is too short, only numbers up to the length of the slice will be returned.
func (Tree) RangeAdd ¶
RangeAdd adds a slice of numbers to the numbers in the tree at index i and subsequent indices.
func (Tree) RangeMul ¶
RangeMul multiplies a slice of numbers with the respective numbers in the tree, starting at index i.
func (Tree) RangeNumbers ¶
RangeNumbers returns in the buf variable a slice of numbers, as defined by the given boundaries. The upper bound is not included. If the lo index is out of boundaries, zero will be returned.
func (Tree) RangeScale ¶
RangeScale scales all numbers in the [lo, hi) range of the tree with the given multiplier. If lo/hi are outside the boundaries of the tree, the [lo, hi) range will be intersected with the tree range.
func (Tree) RangeShift ¶
RangeShift adds the given value to all numbers in the [lo, hi) index range of the tree. If lo/hi are outside the boundaries of the tree, the [lo, hi) range will be intersected with the tree range.
func (Tree) RangeSum ¶
RangeSum returns the prefix sum of the [lo, hi) range. In case of a partial overlap of the range with the tree, RangeSum will return the prefix sum of the intersection of the given interval with the interval of the tree.
func (*Tree) Reset ¶
func (t *Tree) Reset()
Reset initializes the length of the tree to zero, but keeps the backing store. After Reset, the tree can be re-used with Append.
func (Tree) SearchSum ¶
SearchSum returns the largest index and corresponding prefix sum that is smaller than or equal to the given value. In case the tree is empty, -1 is returned.This operation assumes the prefix sums to increase monotonically.
func (Tree) Set ¶
Set sets a number at a given index. If the index is outside of the tree, no updates are made.
Source Files