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.

It can also perform point updates in $\text{O(log N)}$ time. However, it does not support range updates; 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.

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 change 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^{nd}$ position, so we add $1$ to that position

$$0110 + 0010 = 1000$$

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

Java

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

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^{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 - (i & -i);
}

Build Fenwick Tree

Let's create a fenwick tree for input array

$$\begin{bmatrix} 1, 3, 4, 13, -4, 44, -3 \end{bmatrix}$$

Generate a new array with a length one greater than the input array, initializing all elements to 0. Fenwick tree array after adding $1^{st}$ element

Fenwick tree array after adding $2^{nd}$ element

Fenwick tree array after adding $3^{rd}$ element

Fenwick tree array after adding $4^{th}$ element

Fenwick tree array after adding $5^{th}$ element

Fenwick tree array after adding $6^{th}$ element

Fenwick tree array after adding $7^{th}$ element

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

The Fenwick tree we generated earlier enables range operations, particularly range sum calculations in $O(log N)$ time.

Let's calculate range sum from $4$ to $6$.

First we will start with calculate the prefix sum from $3$. Starting with index $4$ in the Fenwick Tree, we will add elements at each step, and move towards $0$.

Therefore prefix sum from $3$ will be $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$.

Now let's calculate the prefix sum from $6$.

Therefore prefix sum from $6$ will be $58$.

Now, to compute the range sum from $4$ to $6$, subtract the prefix sum at index $3$ from the prefix sum at index $6$, which gives us answer as $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

To update an element in a Fenwick tree, we follow a similar process as adding an element. However, instead of adding the actual element, we add a delta value.

Let's update $0^\text{th}$ index in an input array to $3$.

Delta at $0^\text{th}$ index is $3 − 1 = 2$ , so we start by adding $2$ starting from $1$ 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);
}

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