Fenwick Tree

This page provides links to solutions that use the Fenwick Tree data structure.

Overview

The Fenwick Tree, also known as the Binary Indexed Tree, is a data structure that can perform range operations such as finding the total, minimum, or maximum value in $\text{O(log N)}$ time over a range of an array.

It can also perform point updates in $\text{O(log N)}$ time. However, it does not support range updates and in such cases, a segment tree should be used instead. Despite being called a tree, the Fenwick tree is actually stored as an array of elements.

Build Fenwick Tree

Let's create a fenwick tree for input array

$$[1, 3, 4, 13, -4, 44, -3]$$

To create a Fenwick tree, you need two functions called Get Parent and Get Child. These functions help you determine which index to update next when you add or update an element in the Fenwick tree.

Get Parent Function

Get parent function generates the parent index by adding $1$ to the last set bit from the right. Let's calculate parent of $6$ which is represented as $0110$ in binary format. The first set bit from right is in $2^{\text{nd}}$ position, so we add $1$ to that position as below:

$$0110 + 0010 = 1000$$

Therefore, the parent of $6$ is $8$.

Java

public int getParent(int index) {
  return index + (index & -index);
}

Get Child Function

Similarly, get_child function generates the child index by substracting $1$ from the last set bit from the right. Let's calculate child of $6$ which is represented as $0110$ in binary format. The first set bit from right is in $2^{\text{nd}}$ position, so we substract $1$ from that position

$$0110 - 0010 = 0100$$

Therefore, the child of $6$ is $4$.

Java

public int getChild(int index) {
  return index - (index & -index);
}

Let's begin building the Fenwick Tree by generating a new array with a length one greater than the input array and initializing all its elements to 0.

Adding first element $1$ from input array to fenwick tree.

Adding second element $3$ from input array fto fenwick tree.

Adding third element $4$ from input array to fenwick tree.

Adding fourth element $13$ from input array to fenwick tree.

Adding fifth element $-4$ from input array to fenwick tree.

Adding sixth element $44$ from input array to fenwick tree.

Adding seventh element $3$ from input array to fenwick tree.

Java

public int[] buildFenwickTree(int[] arr) {
  // create a fenwickTree array
  int[] fenwickTree = new int[arr.length + 1];

  // add element to fenwick tree starting from index i
  for(int i = 1; i < fenwickTree.length; i++) 
    add(arr[i - 1], i);

  // return fenwick tree
  return fenwickTree;
}

private void add(int element, int index) {
  // adding element until end of fenwick tree is reached
  while(index < fenwickTree.length) {
    // add element at current index
    fenwickTree[index] += element;

    // get parent index of current index
    index = getParent(index);
  }
}

Use Fenwick Tree

Let's calculate the range sum from index $4$ to $6$ of original array. To do this, we calculate the prefix sum up to $6$ and subtract the prefix sum up to $3$ from it.

For calculating the prefix sum from index $3$, we use the getChild function to traverse and add all the elements starting from index $4$ down to $0$ as below:

We get prefix sum from index $3$ as $21 + 0 = 21$.

info

Notice how we are starting with index $4$ for calculating prefix sum from $3$ as fenwick tree array start inserting elements from index $1$.

Similarly, let's calculate the prefix sum from index $6$.

We get prefix sum from index $6$ as $-3 + 40 + 21 =58$.

Therefore, range sum from index $4$ to $6$ of original array is:

$$\text{prefix sum from index} 6 - \text{prefix sum from index} 3 = 58 - 21 = 37$$

Java

public int rangeSum(int from, int to) {
  prefixSum(to + 1) - prefixSum(from);
}

private int prefixSum(int element, int index) {
  int sum = 0;
  while(index > 0) {
    // add element at current index
    sum += fenwickTree[index];

    // get child index of current index
    index = getChild(index);
  }
}

Update Fenwick Tree

The process of updating an element in a Fenwick Tree is the same as the process of adding an element to the Fenwick Tree. However, instead of adding the actual element, we add a delta value.

Let's update $0^\text{th}$ index in an original input array to $3$. Delta at $0^\text{th}$ index is $3 − 1 = 2$ , so we start by adding $2$ starting from $1^{\text{st}}$ index in fenwick tree.

Java

private int update(int newValue, int index) {
  // calculate delta value
  int delta = arr[index] - newValue;

  // update value at index in input array to newValue
  arr[index] = newValue;

  // call add function
  add(delta, index);
}

Complexity

Let's say there are $\text{N}$ elements in given input array.

Time Complexity

Time complexity for building a fewnick tree is:

$$\text{O(N log N)}$$

Adding, updating and searching an element in a fenwick tree taks:

$$\text{O(log N)}$$

Space Complexity

Algorithm uses linear space for storing fenwick tree data structure.

$$\text{O(N)}$$

How to Spot These Problems

You can identify fenwick tree problems if the problem requires you to:

• Quickly calculate the sum of elements from the start of an array up to a certain index.

Leetcode Problem Set