The Fenwick Tree (FT) or Binary Indexed Tree (BIT) is an array built to store sums corresponding to another given array. The built array has the same size as the given array, and each position (or node) of the built array stores the sum of some elements of the given array. Since BIT stores partial sums of the given array, it is a very efficient solution for computing the sum of elements of the given array between two given indexes (range sum/queries) by avoiding looping between the indexes and computing the sum.
The BIT can be constructed in linear time or O(n log n). Obviously, we prefer it in linear time, so let's see how we can do this. We begin with the given (original) array that can be (the subscripts represent the index in the array):
3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)
The idea of building the BIT relies on the Least Significant Bit (LSB) concept. More precisely, let's assume that we are currently dealing with the element from the index, a. Then, the value immediately above us must be at index b, where b = a + LSB(a). In order to apply the algorithm, the value from index 0 must be 0; therefore the array that we operate is as follows:
0(0), 3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)
Now, let's apply a few steps of the algorithm and let's populate the BIT with sums. At index 0 in BIT, we have 0. Furthermore, we use the b = a + LSB(a) formula to compute the remaining sums, as follows:
- a = 1: If a = 1 = 000012, then b = 000012 + 000012 = 1 + 1 = 2 = 000102. We say that 2 is responsible for a (which is 1). Therefore, in BIT, at index 1, we store the value 3, and, at index 2, we store the value sum, 3 + 1 = 4.
- a = 2: If a = 2 = 000102, then b = 000102 + 000102 = 2 + 2 = 4 = 001002. We say that 4 is responsible for a (which is 2). Therefore, in BIT, at index 4, we store the value sum, 8 + 4 = 12.
- a = 3: If a = 3 = 000112, then b = 000112 + 000012 = 3 + 1 = 4 = 001002. We say that 4 is responsible for a (which is 3). Therefore, in BIT, at index 4, we store the value sum, 12 + 5 = 17.
- a = 4. If a = 4 = 001002, then b = 001002 + 001002 = 4 + 4 = 8 = 010002. We say that 8 is responsible for a (which is 4). Therefore, in BIT, at index 8, we store the value sum, 13 + 17 = 30.
The algorithm will continue in the same manner until the BIT is complete. In a graphical representation, our case can be shaped as follows:
In code lines, the preceding flow can be shaped as follows (values are the given array):
public class FenwickTree {
private final int n;
private long[] tree;
...
public FenwickTree(long[] values) {
values[0] = 0 L;
this.n = values.length;
tree = values.clone();
for (int i = 1; i < n; i++) {
int parent = i + lsb(i);
if (parent < n) {
tree[parent] += tree[i];
}
}
}
private static int lsb(int i) {
return i & -i;
// or
// return Integer.lowestOneBit(i);
}
...
}
Now, the BIT is ready and we can perform updates and range queries.
For example, in order to perform range sums, we have to fetch the corresponding ranges and total them up. Consider a few examples on the right-hand side of the following diagram to quickly understand this process:
In terms of code lines, this can be easily shaped as follows:
public long sum(int left, int right) {
return prefixSum(right) - prefixSum(left - 1);
}
private long prefixSum(int i) {
long sum = 0L;
while (i != 0) {
sum += tree[i];
i &= ~lsb(i); // or, i -= lsb(i);
}
return sum;
}
Moreover, we can add a new value:
public void add(int i, long v) {
while (i < n) {
tree[i] += v;
i += lsb(i);
}
}
And we can also set a new value to a certain index:
public void set(int i, long v) {
add(i, v - sum(i, i));
}
Having all these features in place, we can create the BIT for our array as follows:
FenwickTree tree = new FenwickTree(new long[] {
0, 3, 1, 5, 8, 12, 9, 7, 13, 0, 3, 1, 4, 9, 0, 11, 5
});
And then we can play with it:
long sum29 = tree.sum(2, 9); // 55
tree.set(4, 3);
tree.add(4, 5);