Fenwick Tree (Binary Indexed Tree) Data Structure

Why Fenwick tree?

Suppose we are given an array of integers and need to find the range sum between index i and j. One way to solve this problem is to use a single loop. This has a time complexity of O(j - i), or O(n) in the worst case. While this single-loop approach is easy to implement, but it is not efficient in terms of time.

Now, suppose we need to find the range sum between any two indices in an array multiple times. One approach would be simply repeating the process described above for each query. But in the worst case, this would result in a time complexity of m * O(n) or O(mn). This is a brute force approach! Now the critical question is: Can we think of some efficient strategy to improve the time complexity?

If we have the prefix sum of the array up to indices 0 to i - 1 and 0 to j, we can calculate the range sum between indices i and j by subtracting the prefix sum of 0 to i-1 from the prefix sum of 0 to j i.e. Sum[i, j] = PrefixSum[0, j]  -  PrefixSum[0, i   - 1]. This will take O(1) time if we know both values of the prefix sum.

But if we have multiple range sum queries, we don't want to recalculate the prefix sum every time. One solution is to create a prefix sum array that stores the prefix sum of all indexes in the original array. This can be done using a single loop in O(n) time.

Once we have the prefix sum array, we can easily find the range sum between any two indices in O(1) time by using this formula: Sum between index [i, j] = PrefixSum[j]  - PrefixSum[i  - 1]. This will help us to efficiently answer multiple range sum queries without having to recalculate the prefix sum each time.

Pseudocode for range sum query using prefix array

constructPrefixSum(array)
    // PrefixSum[0] represent the sum of zero elements.
    prefixSum = array of zeros with length array.length + 1
    // Build cumulative sums
    for i from 0 to array.length - 1
        prefixSum[i + 1] = prefixSum[i] + array[i]

    return prefixSum


rangeQuery(prefixSum, i, j)
    // Return the sum of array[i] to array[j], inclusive.
    return prefixSum[j + 1] - prefixSum[i]


update(array, i, value)
    // Replace the value at index i.
    array[i] = value
    // Rebuild the prefix sums to reflect the updated array.
    prefixSum = constructPrefixSum(array)

    return prefixSum

There is an issue when using a prefix sum array. Suppose we want to change the value of a single element in the original array. This can be done in O(1) time, but it would require reconstruct the prefix sum array in order to maintain its accuracy. This reconstruction process would take O(n) time.

Suppose, if there are m update queries and m range sum queries.

  • Time complexity of update queries = m * time complexity of constructing prefix array = m * O(n) = O(mn). 
  • The time complexity of range sum queries = m * O(1) = O(m)

As we have seen, the prefix sum array solution has a faster time complexity for finding range sums (O(1)) but a slower time complexity for update queries (O(n)). On the other hand, the Fenwick tree solution has a slower time complexity for finding range sums (O(logn)) but a faster time complexity for update queries (O(logn)).

In situations where there are frequent update queries, Fenwick tree solution will be more suitable as it has a faster time complexity. Overall, Fenwick tree offers a good trade-off between the time complexity of update queries and finding range sums.

What is Fenwick Tree?

The Fenwick tree, also known as a Binary Indexed Tree (BIT), is a data structure that was first described in a paper by Peter M. Fenwick in 1994. It is useful for efficiently calculating range sums and updating element values in an array.

Fenwick Tree Problem Description

Let arr[] be an array of integers of length n and f is a sum function for finding the range sum between any two indexes l and r. f(arr, l, r) = arr[l] + arr[l+1] + …… + arr[r].

The Fenwick tree has the following specifications:

  • It can calculate the value of function f in the range [l, r] in O(logn) time.
  • It can update the value of an element in arr in O(logn) time.
  • It has a space complexity of O(n).

The following image represents the Fenwick tree.

Fenwick tree visualization

In a Fenwick tree, each cell is responsible for a range. The range of responsibility for a cell is determined by the position of the first set bit from the right in the binary representation of the cell's index. This position is known as the rightmost set bit (RSB). If the rightmost set bit is in position p, then the cell is responsible for a range of 2^(p - 1) values.

For example:

  • The RSB for cell 1 is 1, so its range of responsibility is 2^(1 - 1) = 2^0 = 1. This means that cell 1 is responsible for itself.
  • The RSB for cell 2 is 2 (binary representation of 2 is 10). So its range of responsibility is 2^(2 - 1) = 2^1 = 2. This means that cell 2 is responsible for itself and cell 1.
  • The RSB for cell 4 is 3 (binary representation of 4 is 100). So its range of responsibility is 2^(3 - 1) = 2^2 = 4. This means that cell 4 is responsible for itself and cells 1, 2, and 3.
  • The RSB for cell 12 is 3 (binary representation of 12 is 01100). So its range of responsibility is 2^(3 - 1) = 2^2 = 4. This means that cell 12 is responsible for itself and cells 9, 10, 11 and 12.

The following table represents the range of responsibility for numbers from 1 to 16.

Binary representation of Fenwick tree Part 1

A Fenwick tree stores partial sums in a one-based array fenwick[]. Each cell fenwick[i] is responsible for a range of values from the original array, ending at index i. Let’s calculate the value of the range for each cell.

  • lowbit(i) is the value of the rightmost set bit in i. If the rightmost set bit of i is at position p, then lowbit(i) = 2^(p - 1). For example, 12 = 1100₂ has its rightmost set bit at position 3, so lowbit(12) = 2^(3 - 1) = 4.
  • rangeStart(i) = i - lowbit(i) + 1.

Then cell fenwick[i] stores the sum of the original array values from rangeStart(i) through i, inclusive: fenwick[i] = sum(arr[j]), for rangeStart(i) <= j <= i. For example, lowbit(12) = 4, so fenwick[12] stores the sum of array[9] through array[12].

Since the height of the Fenwick tree is log(n), the update and query operations take a maximum of log(n) time. This makes the Fenwick tree a useful data structure for efficiently performing range sum calculations and element updates in an array. Note: We will explain the construction of Fenwick tree later. For now, suppose we have our Fenwick tree ready.

Calculating range sum query using Fenwick Tree

To compute the prefix sum from index 1 to index i in a one-based Fenwick tree, we start with answer = 0. Here, each visited tree cell contributes a range of values to the prefix sum.

  1. Set answer = 0.
  2. While i > 0:
    • Add fenwick[i] to answer.
    • Set i = i - lowbit(i), where lowbit(i) is the value of the rightmost set bit.
  3. Return answer.

To find the prefix sum till index 5, we start with answer = 0 and i = 5.

  • Add fenwick[5] to answer. Since lowbit(5) = 1, this cell covers index 5. Then set i = 5 - 1 = 4.
  • Add fenwick[4] to the answer. Since lowbit(4) = 4, this cell covers indices 1 through 4. Set i = 4 - 4 = 0.
  • The process stops when i reaches 0. The sum of fenwick[5] and fenwick[4] gives the prefix sum of the original array from index 1 through index 5.

Similarly, do the same thing for finding prefix sum of [1, 15]. See the following table to understand how prefix sum up to 15 is calculated. The green regions are the ones that are used to find the answer.

Binary representation of Fenwick tree Part 2

So to find the prefix sum up to index 15, the answer would be equal to the sum of fenwick[15], fenwick[14], fenwick[12], and fenwick[8]. Their ranges are:fenwick[15] covers index 15, fenwick[14] covers indices 13–14, fenwick[12] covers indices 9–12 and fenwick[8] covers indices 1–8.

The time complexity of computing the prefix sum using a Fenwick tree is O(log n), as we need a maximum of log(n) (the maximum number of set bits) operations to find the prefix sum. Once we have computed the prefix sum, we can use the formula rangeSum[i, j] = prefixSum[j] - prefixSum[i-1] to find the range sum for any range [i, j]. This formula takes O(1) time to compute.

Pseudocode for fenwick tree range sum query

prefixSum(i)
    answer = 0
    while i > 0
        answer = answer + fenwick[i]
        i = i - lowbit(i)

    return answer


rangeQuery(i, j)
    return prefixSum(j) - prefixSum(i - 1)

Where lowbit(i) returns the range of responsibility of i, where lowbit(i) = 2^(RSB(i) - 1).

Point updates in Fenwick Tree

A point update changes one value in the original array. To reflect that change in the Fenwick tree, we add the change amount to every cell whose range includes the updated index. So starting at index i, we move through those cells with i = i + lowbit(i) until the index exceeds the array size.

To update a value in Fenwick tree, first find its index i in the original array and calculate the change, delta.

  1. Update the original array element by adding delta.
  2. Add delta to fenwick[i].
  3. Move to the next cell that includes this element: i = i + lowbit(i).
  4. Repeat steps 2–3 while i is within the tree.

If replacing the element with a new value, calculate delta = newValue - oldValue before applying the update.

Fenwick tree point update visualization

As shown in the image, to increase the value at index 9 in the original array by x, we propagate the update from index 9 to 10, from 10 to 12, and from 12 to 16. The required updates are:fenwick[9] += x, fenwick[10] += x, fenwick[12] += x, and fenwick[16] += x.

For example, suppose we want to add 5 to the element at index 3 in the original array. We first update that element, then propagate the change through the Fenwick tree by moving to the next cell using i = i + lowbit(i). Starting at index 3, we add lowbit(3) = 1 to get index 4. Next, we add lowbit(4) = 4 to get index 8. We continue this process until we reach the end of the tree, updating fenwick[i] += 5 at each index.

By adding the range of responsibility to the current index at each step, we propagate the change upward through the tree to the cells responsible for the current cell.

Pseudocode for fenwick tree point update

pointUpdate(i, x)
    array[i] = array[i] + x
    while i <= n
        fenwick[i] = fenwick[i] + x
        i = i + lowbit(i)

The time complexity of the Fenwick tree point update is O(log n), similar to the prefix sum query.

How to construct the Fenwick tree?

This is the first step to perform before answering any range-sum or point-update queries. You can initialise the tree with all zeros and then perform a point update for each index, which takes O(n log n) time. But we can do better and construct the Fenwick tree in O(n) time.

To build a Fenwick tree in O(n), we process its cells from left to right. For each cell at index i, we pass its accumulated value to the next cell that contains its range: parent = i + lowbit(i). If parent is within the tree, we add fenwick[i] to fenwick[parent]. This is similar to a point update, but each cell passes its accumulated sum to its parent only once. As the process continues, those sums cascade through the tree.

To construct a Fenwick tree in linear time, we can follow these steps:

  1. Initialise every cell to 0.
  2. Move through the original array from left to right. For each value array[i], add it to fenwick[i].
  3. Now we find the next cell that contains the range represented by fenwick[i]:
    parent = i + lowbit(i).
  4. If parent is within the tree, we add fenwick[i] to fenwick[parent].
  5. We continue until processing of all indices is done.

Note: Each cell first receives its own array value, then passes its accumulated range sum to its parent.

Pseudocode for construction of Fenwick tree

buildFenwickTree(array)
    n = length of array
    fenwick = array of zeros with length n + 1
    // Copy each value into 1-based Fenwick index.
    for i from 1 to n
        fenwick[i] = array[i - 1]

    // Pass each cell accumulated sum to its parent.
    for i from 1 to n
        parent = i + lowbit(i)

        if parent <= n
            fenwick[parent] = fenwick[parent] + fenwick[i]

    return fenwick

Why does the above idea work? Here is an insight: Before index i passes its value to its parent, it has already received the sums of earlier cells whose ranges combine to form its own range. So fenwick[i] holds its complete range sum when it is propagated. Note: For a 1-based index i, fenwick[i] stores the sum over range [i - lowbit(i) + 1, i].

For example: Lets consider fenwick[8] for the array [1, 2, 3, 4, 5, 6, 7, 8]. It must store the sum of elements at indices 1 through 8. It starts with the value 8. Index 4 passes its accumulated sum, 1 + 2 + 3 + 4 = 10. Then Index 6 passes its accumulated sum, 5 + 6 = 11. Finally, Index 7 passes its value 7. So fenwick[8] = 8 + 10 + 11 + 7 = 36, the sum of the entire array. Each contribution reaches index 8 through the parent links.

How does RSB work?

The RSB is the position of the rightmost set bit in the binary representation of a number and lowbit(i) is the value of the RSB. If the rightmost set bit is in position p, lowbit(i) = 2^(p - 1). In a simple way, we can find the value of lowbit(i) by using the bitwise AND operator with the negative of the number. This works because the negative of a number is produced by inverting the bits of the number and then adding 1 (2's complement representation). In other words, the bitwise expression i AND (-i) isolates the rightmost set bit.

lowbit(i)
    // Return the value of the rightmost set bit in i.
    return i AND (-i)

Fenwick Tree Java Implementation

class FenwickRangeQueryPointUpdate
{
    private final int size;
    private final int[] tree;
    private final int[] values;

    public FenwickRangeQueryPointUpdate(int[] initialValues)
    {
        size = initialValues.length;
        values = initialValues.clone();
        tree = new int[size + 1];

        // Copy values into the one-based Fenwick tree.
        for (int i = 1; i <= size; i++)
            tree[i] = values[i - 1];

        // Build the tree in O(n) time.
        for (int i = 1; i <= size; i++)
        {
            int parent = i + lowbit(i);
            if (parent <= size)
                tree[parent] += tree[i];
        }
    }

    // Set the value at the zero-based index to newValue.
    public void update(int index, int newValue)
    {
        int delta = newValue - values[index];
        values[index] = newValue;

        for (int i = index + 1; i <= size; i += lowbit(i))
            tree[i] += delta;
    }

    // Return the sum from left through right, inclusive.
    public int query(int left, int right)
    {
        return prefixSum(right + 1) - prefixSum(left);
    }

    // Return the sum of the first count values.
    private int prefixSum(int count)
    {
        int sum = 0;

        for (int i = count; i > 0; i -= lowbit(i))
            sum += tree[i];

        return sum;
    }

    private static int lowbit(int i)
    {
        return i & -i;
    }
}

Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms.

Find us on:

Self-paced Courses and Blogs