> Interview Breeze

Fenwick Tree (Binary Indexed Tree)

What is a Fenwick Tree?

A Fenwick Tree, also known as a Binary Indexed Tree, is a tree structure that allows for a balanced load between updates and summations when trying to efficiently calculate prefix sums (Log(N) update, insert, and N*Log(N) for creation).

Building the tree

The first component to understand about a Fenwick tree is how we store the data. Unlike the linked node objects you might commonly create for other tree structures, we will use an array to store all of our values. The array will be 1 element larger than the number of elements in the tree, and the 0'th index will be empty as it will be our root node in this tree structure. This means that we also offset everything in our real array by 1 (so it becomes 1 indexed in the tree's array instead of 0 indexed.)

To figure out which indexes become the children of which other indexes, we will use a bit flipping strategy. We take the current index, and flip it's right most bit that is set to 1 to get the parent index. For example, the binary representation of 8 is 1000. If we flip the right most set bit, we get 0000 which is 0 (the root node). For the index 9, we have the binary representation of 1001. If we flip the right most set bit, we get 1000, which is the number 8. If we imagined we had 10 indexes of an array as a Fenwick tree, it would be represented like so:

Fenwick tree with 10 nodes

To bit flip an index in code is pretty straight forward. We take the bit-wise AND of our current index and it's negative, then subtract that from our current index value.

# get the parent node index by flipping the right most bit
index -= index & -index

How to represent prefix sums in the tree

We can imagine that every number can be represented as a power of 2. For example 10 can be represented as 23 + 21, and 13 can be represented as 23 + 22 + 20. A Fenwick tree uses these powers of 2 to determine what prefix sum is stored in each node. For example, index 8 can be represented as 0 + 23 (the 0 is from our root node).

As another example, take the index 9, which can be represented as 0 + 23 + 20. We add everything except the last element to get our start index 0 + 23 == 8, and the value of the last element in the equation 20 == 1 to determine how many elements from that index we should sum (in this case, we only use the single value at the index). In the case of index 10, we would have 23 + 21, which equates to summing 2 elements starting from the index of 8.

What you will see as you look at the summations, is that each node contains the sum of all elements from it's index to it's parent's index. Working with that, if you want to get the prefix sum to a specific index, you would simply sum the value of that index node and all of it's parents (which happen to be all of the other powers of two in the equation). Combining this knowledge with the bit flipping above, what you will notice is that our right most bit flipping is essentially us figuring out all the power of twos needed for our equation.

Putting it all together

Using our knowledge of how to build the fenwick tree, we can implement the code for it in a fairly straight forward fashion:

class FenwickTree():

    def __init__(self, values):
        self.size = 1 + len(values)
        self.data = [0] * self.size
        for index, value in enumerate(values):
            self.add(index + 1, value)

    def add(self, index, value):
        if index > 0:
            while index < self.size:
                self.data[index] += value
                index += index & -index

    def sum(self, index):
        if index > 0:
            result = 0
            while index > 0:
                result += self.data[index]
                index -= index & -index
            return result
        return 0

You may also want to read:

Array Summing

Given an array containing N integers, write a class that contains two functions: and update function that will update a value at a given index, and a sum function that will sum all values between indexes I1 and I2.

How to Implement a Quadtree in Python

A Quadtree is a data structure that allows two dimensional data, such as images or matrices, to be represented and traversed as a tree.

Reverse a singly linked list

Given a singly linked list, write a function that returns a linked list with all the nodes in reverse order.