Fenwick Tree(Binary Indexed Tree) Explained

7 min readMay 18, 2023

Fenwick tree, also called a binary indexed tree (or just BIT abbreviated), is a tree data structure that can efficiently update elements and calculate range sums on a list of numbers.

Fenwick tree was first described in a paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).

Fenwick tree is a data structure which:

calculates the value of function f in the given range [L, R] in O(log N) time;
updates the value of an element of A in O(log N) time;
requires O(N) memory, or in other words, exactly the same memory required for original array;
is easy to use and code, especially, in the case of multidimensional arrays.

Here are some typical problems of Fenwick Tree (Binary Indexed Tree).

Problem

Let’s start with a mutable range sum query problem.

Given an array of numbers A = {A1, A2, …, An} with starting index of 1, we have two operations:

Sum(L , R), we calculate the sum of numbers between positions L and R inclusive.
Update(x, value), we change the value of the element at the index x to be value.

Our goal is to implement these two operations efficiently.

Method 1: Brute force

There are some algorithms to solve this problem, the first one is brute force, which is the easiest way to think of.

The time complexity for brute force is obvious:

for query: O(n), because we need to accumulate each number of closed interval [L, R].
for update: O(1), we can directly find the number to be updated and update it.

Method 2: Prefix sum array

Create an array called pre and compute prefix sum of array A:

pre[0] = 0 (for the convenience of calculation)
pre[1] = A[1]
pre[2] = A[1] + A[2]
…
pre[n] = A[1] + A[2] + A[3]+ … + A[n]

For query operation, we can easily get the result from prefix sum array pre using the equation A[L]+ A[L+1] + … + A[R] = pre[R] − pre[L−1].

For example, if we want to get the sum of closed interval [1, 3], we can directly get the result using pre[3] — pre[0].

The time complexity for this algorithm:

Query: The time complexity is reduced to O(1), only one subtraction is needed.
Update: However, if we want to modify the value of a[k], we also need to modify the values of pre[k], pre[k+1], pre[k+2]… and the time complexity is increased to O(n).

Thought process

We found that when we change the time complexity of one operation to O(1), the time complexity of the other operation will become O(n).

When there are a lot of query and update operations, no matter which method is used, the overall time complexity will not be fast.

So is there a way to reduce the time complexity of both operations at the same time?

In the field of algorithms, constructing clever data structures is a common method to reduce time complexity.

Therefore, to solve this problem more efficiently, we can use a binary indexed tree. It takes only O(log n) time for both update and sum operations. If we have O(n) update and sum operations, the overall time complexity will be O(n log n).

Core Idea

Let’s take an example: How do we calculate the prefix sum of A[1…7]?

The simplest way is to add up the 7 numbers: A1 + A2 + A3 + A4 + A5 + A6 + A7

But if we know in advance that A = the sum of A[1…4], B = the sum of A[5…6], and C = the sum of A[7…7] (which is actually just a[7] itself). The answer is obviously A + B + C, we just need to find the sum of three numbers.

This is why a binary indexed tree can quickly compute information: We can always divide a prefix range [1, n] into no more than log(n) intervals, with the information of these log(n) intervals already known.

Therefore, we only need to merge the information of these log(n) intervals to get the answer. Compared to merging n pieces of information directly, this method is much more efficient.

It is easy to see that the information must satisfy the associative law, otherwise we cannot merge them as described above.

The following picture shows how BIT works:

The eight squares at the bottom represent the original data array A. The squares above represent the sum array of array A.

The sum array is used to store the sum of a certain range of elements in the original array A. In other words, the information of these ranges is known, and our goal is to break down the query prefix into these small ranges.

For example, from the figure, it can be seen that: sum[2] covers A[1 … 2]; sum[4] covers A[1 … 4]; sum[6] covers A[5 … 6]; sum[8] covers A[1 … 8]; the remaining sum covers a itself (which can be considered as A[x, x], a small range with a length of 1).

Rules of BIT

It is not difficult to find that sum[x] must govern the total information of an interval whose right boundary is x。

So the question is, what is the left boundary of the interval governed by sum[x] (x >= 1)?? In other words, what is the length of the interval it governs?

In the binary indexed tree, the length of the range governed by sum[x] is defined as 2^k , where:

Let the lowest bit in binary be the 0th bit, then k is exactly the position of the lowest 1 in the binary representation of x;
2^k (the length of the range governed by c) is exactly the number composed of the lowest 1 and all subsequent 0s in the binary representation of x.

For example, which range is governed by sum[88]?

Since

the lowest 1 and all subsequent 0s in its binary representation is 1000, which is 8 in decimal, so sum[88] governs 8 elements in array A. Therefore, sum[88] represents the range information of A[81 … 88].

Let the number formed by the lowest bit 1 of x and all the following 0s in binary be lowbit(x).

Then the interval governed by sum[x] is A[x-lowbit(x)+1, x].

lowbit

Lowbit(x) actually extracts the lowest bit 1 of x. In other words, lowbit(x)=2^k, where k has the same meaning as above.

The calculation method for lowbit is

int lowbit(int x)
{
    return x&(-x);
}

By inverting all the bits of x’s binary encoding and adding 1, we can obtain the binary encoding of -x, then calculate x & (-x).

For example, the binary encoding of 6 is 110. Inverting all the bits results in 001, and adding 1 gives 010.

Therefore, lowbit(6) = 110 & 010 = 010, which is 2. Thus, the range governed by 6 is the closed interval [6 - 2 + 1, 6].

Query Interval sum

In fact, any interval query can be done this way: the sum of A[L, R] can be found by subtracting the sum of A[1 … L-1] from the sum of A[1 … R], thus transforming the interval problem into a prefix problem, which is easier to handle.

For instance, if we want to query the sum of interval A[4 … 7], we break it down into two sub-processes: querying the sum of A[1 … 7] and querying the sum of A[1 … 3], and finally taking their difference.

How do we do prefix queries? Reviewing the process of querying A[1 … 7]:

We start by jumping backward from sum[7] and find that sum[7] only covers the element A[7]
Then, we look for sum[6] and find that it covers A[5 … 6]
We then jump to sum[4] and find that it covers A[1, … 4]
When we try to jump to sum[0], we find that it does not exist and stop.

The sum we just found are sum[7], sum[6], and sum[4], which are actually the three small intervals that A[1 … 7] is divided into. Combining them, the answer is sum[7] + sum[6] + sum[4].

Looking at the process above, every time we jump backward, we must jump to the left endpoint of the current interval minus one, which becomes the right endpoint of the new interval, in order to split the prefix without overlapping or leaving any element out.

For example, if sum[6] covers A[5, 6], the next jump will be to 4.

Here is the C++ code for query A[1, x]:

int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x))
        res += sum[x];
    return res;
}

Start from sum[x] and jump backwards, where sum[x] covers sum[x-lowbit(x)+1 … x];
Update x to x - lowbit(x), if x=0, exit the loop; Otherwise, go back to step 1.
Merge the visited sum as return value.

Update

Now let’s consider how to modify A[x] in a single point.

To ensure efficiency, we only need to modify all sum[y] in charge of A[x], because other sum values obviously haven’t changed.

The sum[y] that governs A[x] must include sum[x] (according to property 1), so y is the ancestor of x in the binary indexed tree. Therefore, we can start from x and jump to its parent.

For example, as shown in the following figure, to achieve A[5] += val, the sum[5], sum[6], and sum[8] need to be updated.

Here is the C++ code for implementing A[x] += val :

 void Update(int x, int val)  
{
    for (; x < N; x += lowbit(x)) 
        sum[x] += val;
}

Let N represent the size of A.

If x ≥ N, it means that the end has been reached and the loop is terminated.
Otherwise, update sum[x].
Update x to x + lowbit(x).

Conclusion

This article introduces the basic principles and implementation methods of Fenwick Tree (Binary Indexed Tree). This data structure is mainly used in problems related to intervals.

Compared with segment tree, the code of BIT is much shorter than that of segment tree, and the time efficiency constant is also smaller, so its usage is also very wide.