Understanding Fenwick Tree (Binary Indexed Tree)

1. Introduction

A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.

2. Problem Description

Let’s start with a mutable range sum query problem. Given an array of numbers $A = \{A_1, A_2, ..., A_n\}$ with starting index of $1$ , we have two operations: $update$ and $sum$ . For an $update$ operation, $update(i , value)$ , we change the value of the element at the index $i$ to be $value$ . For a $sum$ operation, $sum(left , right)$ , we calculate the sum of numbers between positions $left$ and $right$ inclusive. Our goal is to implement these two operations efficiently.

3. Brute Force Solution

For the $update$ operation, we can directly update the array element at the specified location. For the $sum$ operation, we can iterate the array from index $left$ to $right$ and sum each element:

In this solution, the $update$ operation takes $O(1)$ time and $sum$ operation takes $O(n)$ time. The space requirement is $O(1)$ .

4. Prefix Sum Solution

In order to have a faster $sum$ operation, we can use the prefix sum approach. For the input array of numbers $A = \{A_1, A_2, ..., A_n\}$ , the prefix sum at index $i$ is the sum of the prefix numbers ending at $i$ :

Based on the prefix sum definition, we can calculate a range sum with two prefix sums:

Given an array of numbers $A = \{A_1, A_2, ..., A_n\}$ , let’s first construct a prefix sum array from $A$ :

For the $sum$ operation, we can directly answer the query with two prefix sum values. However, we need to update the prefix sum array for the $update$ operation:

In this solution, the $update$ operation takes $O(n)$ time and $sum$ operation takes $O(1)$ time. The space requirement is $O(n)$ as we need an array to store prefix sums.

5. Fenwick Tree Solution

For the brute force and prefix sum solutions, either $update$ or $sum$ operation takes $O(n)$ time. If there are multiple $update$ and $sum$ operations, these two solutions will take a lot of time. For example, if we have $O(n)$ numbers of $update$ and $sum$ operations, the overall time complexity will be $O(n^2)$ for both solutions.

We can use a Fenwick tree to solve this problem more efficiently, as it only takes $O(logn)$ time for both $update$ and $sum$ operations. Therefore, if we have $O(n)$ numbers of $update$ and $sum$ operations, the overall time complexity will be $O(nlogn)$ .

5.1. Range of Responsibility

When we make an $update$ operation, we have an input index parameter, $i$ , to indicate the update element location. Similarly, when we make a $prefixSum$ operation, we have an input index parameter, $i$ , to indicate the sum of the prefix numbers ending at $i$ . In the Fenwick tree solution, we do both operations based on the binary form of the input index $i$ . That’s the reason why we also call it a binary index tree.

In a Fenwick tree, each index has a range of responsibilities. We calculate the range of responsibility value based on the position of the rightmost set bit (RSB) in the binary representation of the index. For example, the binary representation of $11$ is $(1011)_2$ . The range of responsibility of $11$ is then $1$ as its RSB gives value $(1)_2 = 1$ . Another example of a range of responsibilities is for the number $12 =(1100)_2$ . The range of responsibility of $12$ is $4$ as its RSB gives value $(100)_2 = 4$ .

5.2. Range of Responsibility Calculation

In computer science, we use the two’s complement method to produce a negative number from a positive number. Firstly, we reverse the ones and zeros of the binary representation of the positive number. Then we add one. Therefore, we can calculate the range of responsibility value of an index $\textbf{i}$ with the bit operation: $\textbf{i \& (-i)}$ .

For example, the binary value of $12$ in an 8-bit form is $(0000\, 1100)_2$ . After we reverse each bit, we have $(1111\,0011)_2$ . When we add $1$ , every bit $1$ starting at the right will overflow into the next higher bit until we reach a $0$ bit, which is the RSB of the original positive number. Therefore, we can have $-12 = (1111\, 0100)_2$ .

When we do bitwise AND operation on the two numbers, we can get the range of responsibility value: $12 \,\& \,(-12) = (0000\, 1100)_2 \,\& \,(1111\, 0100)_2 = (0000 \,0100)_2 = 4$ .

Let’s define the range of responsibility calculation, $RSB$ , for an index $i$ :

5.3. Fenwick Tree Structure

The basic idea of the Fenwick tree solution is to precompute the responsibility range sum for each index. Then, we can calculate the prefix sum of an index $i$ based on the precomputed Fenwick values. Also, when we update the element at an index $i$ , we can only update those precomputed Fenwick values that cover the index $i$ .

Let $Fenwick[i]$ denote the responsibility range sum for each index $i$ . For the array $A = \{A_1, A_2, ..., A_n\}$ , we can have have an array $Fenwick$ where

The following table shows the Fenwick values for numbers from 1 to 16:

Based on the Fenwick value definition, we can see that one Fenwick value can cover several Fenwick values. For example, $Fenwick[8] = sum(A_1,A_2,...,A_8)$ covers $Fenwick[4]=sum(A_1, A_2, A_3, A_4)$ , $Fenwick[6] = sum(A_5, A_6)$ and $Fenwick[7] = sum(A_7)$ . We can use a tree structure to represent the coverage relationships:

In this Fenwick tree structure, leaf nodes are the index numbers. Each internal node represents a Fenwick value that can be constructed from its children Fenwick values and its own index array number. For example:

$Fenwick[16] =Fenwick[8]+Fenwick[12]+Fenwick[14]+Fenwick[15]+A_{16}$

5.4. Fenwick Tree Construction

To construct a Fenwick tree, we can use a dynamic programming approach by propagating the smaller Fenwick values to the big Fenwick values:

In this algorithm, we first initialize the Fenwick array with the input array $A$ . Then, we use a loop to propagate the smaller Fenwick values to their parent Fenwick values. The time complexity is $O(n)$ .

We only need to construct the Fenwick array once at the beginning. In the future, we only need to update at most $O(logn)$ Fenwick values in an $update$ operation.

5.5. Prefix Sum Calculation

When we compute the prefix sum of index $i$ , we can start from index $i$ and go downwards until we reach $0$ :

In this algorithm, we start from the input index $i$ and add its Fenwick value to the $result$ . Then, we remove the $RSB$ of $i$ and add the new Fenwick value into the $result$ . We keep doing this process until we reach index $0$ .

Suppose we want to find the prefix sum for index $11 = (1011)_2$ . Firstly, we add $Fenwick[11]$ into our $result$ . Then, we subtract the $RSB$ value of $11$ , which is $1$ , and reach a new index $10=(1010)_2$ . Therefore, we add $Fenwick[10]$ into our $result$ . Again, we subtract $RSB(10) = 2$ from $10$ and get a new index $8=(1000)_2$ . Similarly, we add $Fenwick[8]$ into our $result$ . Finally, we subtract $RSB(8)=8$ from the current index $8$ and stop the loop as we reach the index $0$ .

In the end, we can have $prefixSum(11) = Fenwick[11] + Fenwick[10] + Fenwick[8]$ .

The time complexity of this algorithm is $O(logn)$ as we remove one set bit of the original index $i$ in each iteration until we reach $0$ .

5.6. Fenwick Tree Update

The $update$ operation is the opposite of $prefixSum$ operation. We start from the input index $i$ and go upwards along the tree path to propagate the $update$ operation.

Suppose we want to add a $delta$ value at the location $3$ . We can first add $delta$ to $fenwick[3]$ . Then, we get its parent based on the $RSB(3)$ and reach the index $4$ . Therefore we also add $delta$ to $fenwick[4]$ . Similarly, we continue to update the parent Fenwick values like $Fenwick[8]$ and $Fenwick[16]$ until we reach the array size boundary $n$ .

Similar to the $prefixSum$ , the time complexity of $add$ is $O(logn)$ .

5.7. Fenwick Tree Solution

We can combine the above functions to solve the mutable range sum query problem:

In the $update$ function, we first calculate the $delta$ of the updated value, Then, we call the $add$ function to update the Fenwick tree. The time complexity is $O(logn)$ as we only call the $add$ function once.

In the $sum$ function, we call $prefixSum$ function twice to get the sum between $left$ and $right$ . The overall time complexity is still $O(logn)$ .

The space complexity of the Fenwick solution is $O(n)$ as we need to store the Fenwick values for all the indexes.

6. Conclusion

In this article, we showed how to use a Fenwick tree to solve the mutable range sum problem. With the Fenwick tree, we can achieve $O(logn)$ time for both $update$ and $sum$ operations.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex