A Fenwick tree is a data structure that holds an ordered collection and supports the operations sum and update, both in O(log n) time.

In its most basic form the tree stores an array of integers. Sum calculates the cumulative total of the first n integers and update modifies an element. Theoretically one is not limited to addition of integers when using Fenwick trees. We can however limit the discussion of Fenwick trees, without loss of generality, to trees involving integers and summing/updating using addition[1].

See this Github repository for an implementation using multiplication.

Problem Statement

Design a data structure that supports cumulative accumulation of values and also supports modification of the values.

Naive Solution

A naive approach to designing such a data structure may choose to store the values in an array [1, 2, 3, 4, 5]. Summation is then achieved by iterating the array and runs in O(n). Updating a value in the array is done via indexing and quite clearly runs in O(1) or constant time.

Perhaps we may choose to optimize for cumulative summation. This may be done by instead of storing the values, storing the cumulative totals [1, 3, 6, 10, 15]. Summation is now a matter of indexing and runs in 0(1) time. However in order to update a value we must traverse the array from the updated value to the end of the array updating each value as we go. This is, once again 0(n).

Fenwick Tree Solution

The problem that a Fenwick tree solves is the ability to both sum a series and modify it in less that O(n) running time.

According to Wikipedia Paul Fenwick proposed the data structure in 1994. How Mr Fenwick came up with this structure I have no idea but in order to do so he made some very interesting observations. Let us start with a binary search tree with the nodes positioned in such a way that an inorder tree traversal would give the same order as the collection we wish to store. Each node has an associated value.

The first observation is that we can update a node by setting the nodes value and then bubble the new value up the tree updating each internal node’s value iff that node was reached via it’s right child.

Doing so maintains a tree that supports the calculation of cumulative total by using a similar technique, namely; when finding the sum for a node we start with the nodes value then traverse up the tree, adding the internal nodes value as we pass if the node was reached by its left child.

Further explanation can be found in this very nice StackExchange post.

The second observation is that if we take the inorder node position as the node id we can store the tree in an array using the id as the index. It can then be observed that by a feat of bit twiddling genius involving adding and removing the least significant bit we can traverse up the tree. Not only can we traverse up the tree, at each node we can ascertain from which child we arrived. See the above link for a more thorough explanation.

Fenwick Tree in Go

Without further ado

type Fenwick struct {
	tree []int
}

// NewFenwick: Build Fenwick tree to hold n values.
func NewFenwick(n int) *Fenwick {
	fen := &Fenwick{
		tree: make([]int, n),
	}
	return fen
}

Here we abstract the data with a struct. This prevents inadvertent modification of the deceivingly subtle data that makes up the tree. Also, in my opinion, it makes the slice access in later code cleaner since we need not use pointer indirection to index into the array as is sometimes required (*ptr)[i].

// Sum all values upto and including index.
func (fen *Fenwick) Sum(index int) int {
	sum := 0
	index++
	for index > 0 {
		sum += fen.tree[index-1]
		index -= lsb(index)
	}
	return sum
}

// lsb: Least Significant Bit
func lsb(x int) int {
	return x & -x
}

I would love to have gone straight from an understanding of this data structure to the code, however this is not the case. I merely translated the C code from Wikipedia into Go code. Even then, it took a while for me to implement the test cases thoroughly enough that I understood what was going on.

// Update using addition index by value.
func (fen *Fenwick) Update(index, value int) {
	index++
	for index <= fen.Size() {
		fen.tree[index-1] += value
		index += lsb(index)
	}
}

// Size: Number of values stored by tree.
func (fen *Fenwick) Size() int {
	return len(fen.tree)
}

All code available on Github.

Conclusion

Fenwick trees are used, according to Wikipedia, in arithmetic coding. They also find use in counting integer inversion in an array.

In conclusion, the Fenwick tree is a nifty little data structure. Hats off to its creator.


Notes:

[1] Fenwick trees are not limited to integers and addition. Any binary operation may be used. Any data type which implements the binary operation may be stored in the tree.