In this series we’re exploring the data structure - Binary Indexed Tree (BIT) [Fenwick tree], BIT is used for storing frequencies and manipulating cumulative frequencies.
This series includes 3 parts. This is the second part of the series.
1. Binary Indexed Tree (BIT) Part-1
2. Binary Indexed Tree (BIT) Part-2
3. Binary Indexed Tree (BIT) Part-3 [In progress]
Part 2
Like the naive approaches we saw in the previous post, BIT also uses table (one dimensional array) to maintain frequencies. Let us call this as BIT table.
Like CF table, the BIT table stores the sum of frequencies. The difference is:
In CF table, value stored at index j is the sum of frequencies of numbers from 1 through j, inclusive.
In BIT table, value at index j is sum of frequencies of numbers from j - k through j, inclusive. We will define what k is later in this post.
In BIT table, value at index j is sum of frequencies of numbers from j - k through j, inclusive. We will define what k is later in this post.
Let us start with an example BIT table. Below BIT table corresponds to the sample F table we used in the previous post. To make our discussion easy below we have shown F table as well.
BIT[j] stores sum of frequencies of number j and k contiguous numbers before j.
j
BIT[j] = Σ F[a]
a=j-k
For example:
12 12
BIT[12] = Σ F[a] = Σ F[a] = F[9] + F[10] + F[11] + F[12] = 5
a=12-3 a=9
j = 12, k = 3
BIT[12] stores sum of frequencies of number 12 (i.e. F[12]) and 3 contiguous numbers before 12 i.e. F[9], F[10] and F[11].
How k is calculated?
You might have noticed that the value of k is different for different index/number j, for example k is 3 for index 12 and 1 for index 6. In this section we will see how k is calculated for a given index j.
Lets refresh some basics.
In binary representation of a number, each bit position has a positional value. Below tables shows positional values of each bit of the binary number 1100
binary number
|
1
|
1
|
0
|
0
|
Position
|
3
|
2
|
1
|
0
|
Positional value
|
2^3
|
2^2
|
2^1
|
2^0
|
Positional value of a bit in a binary representation can be calculated from the position of the bit, if position of a bit is p then its positional value is 2^p.
The term “least significant 1” of a binary number refers to the first 1 bit from right. For example the “least significant 1” of 1100 is highlighted.
Now lets see how k is calculated for an index j.
Suppose position of “least significant 1” in the binary representation of index j is r, so it’s positional value is 2^r.
The value of k is calculated as:
k = 2^r - 1.
Some examples:
In case of number 12 (1100)
The position r of "least significant 1" is 2, it’s positional value is 2^2.
The position r of "least significant 1" is 2, it’s positional value is 2^2.
The value of k in this case is 2^2 - 1 = 3.
This means BIT[12] stores sum of consecutive frequencies F[12] and 3 (i.e. k) previous frequencies F[11], F[10] and F[9].
In other words B[12] holds sum of 4 (2^r = 2^2) continuous frequencies ending with F[12].
In case of number 13 (1101)
The position r of "least significant 1" is 0, it’s positional value is 2^0.
The position r of "least significant 1" is 0, it’s positional value is 2^0.
The value of k in this case is 2^0 - 1 = 0.
This means BIT[13] stores only 1 frequency which is F[13].
In other words B[13] holds sum of 1 (2^r = 2^0) continuous frequencies ending with F[13].
Let's generalize above finding:
BIT[j] holds sum of 2^r continuous frequencies starting from F[j - 2^r + 1] to F[j] inclusive, where r is the position of "least significant 1" in the binary representation of j
index responsibility
Let's generalize above finding:
BIT[j] holds sum of 2^r continuous frequencies starting from F[j - 2^r + 1] to F[j] inclusive, where r is the position of "least significant 1" in the binary representation of j
index responsibility
Since sum of frequencies of the numbers in the range [j - k ... j] gets stored at index j, we say an index j in BIT table is responsible for indices range [j - k ... j] in F table.
[j - k ... j] = [j - (2^r - 1) ... j] = [j - 2^r + 1 ... j] where r is position of “least significant 1” in j.
Cumulative frequency in BIT
Now we have clear idea about deriving range [ j - 2^r + 1 ... j ] from an index j.
We know BIT[j] stores sum of 2^r contiguous frequencies with last frequency as F[j].
Hence BIT[8] stores sum of 2^r contiguous frequencies with last frequency as F[8], where r = position of "least significant 1" in 8. For 8 (1000), the position r of “least significant 1” is 3, i.e. BIT[8] holds sum of 8 (2^r = 2^3) continuous frequencies ending with F[8].
Hence BIT[8] = F[1] + F[2] + F[3] + F[4] + F[5] + F[6] + F[7] + F[8]
CF(12) = BIT[12] + BIT[8]
What we did to find CF(12) is first we gets value stored at BIT[12] then add this to value stored at BIT[8], but how do we know after getting value from BIT[12] we need to look for BIT[8] ?
It is simple since we know BIT[12] stores sum of 4 (2^r where r is position of “least significant 1” which is 2) consecutive frequencies ending with F[12], next index we need to consider is 12 - 2^2 = 8, BIT[8].
Apply the same logic again, we know BIT[8] stores sum of 8 (2^r where r is position of “least significant 1” which is 3) consecutive frequencies ending with F[8], next index we need to consider is 8 - 2^3, BIT[0]
So CF(12) = BIT[12] + BIT[8] + BIT[0]
The basic idea is: calculating a new index by subtracting 2^r from the old index (where r is the position of “least significant 1” in old index), and repeating this operation until the index is zero.
Subtracting 2^r from an index is equivalent to clearing “least significant 1” of index. For example for index 12 (1100), positional value of r is 2, so 2^r is 4 (100).
(index - 2^r) = (12 - 4) = (1100 - 100) = 8 = 1000
If we clear the "least significant 1" from 12 (1100) we get exactly same result 8 (1000)
With this knowledge we can come up with following implementation of int CumFreq(int m)
int CumFreq(int m) { int cf = 0; while (m > 0){ cf += BIT[m]; m = clearLeastSignificantOne(m); } return cf; } The function 'clearLeastSignificantOne' is a place holder for the logic to clear “least significant 1” from a number, The next section explains how this can be achieved efficiently.
Extracting least significant 1
To find new index from old index, we need an efficient way of clearing “least significant 1” of a number.
This requires extracting “least significant 1”.
For example extracting “least significant 1” from the binary number 101011000 result 000001000.
Once we extract the “least significant 1”, we can clear “least significant 1” from the original number as:
101011000 -
000001000
---------------
101010000
How do we extract “least significant 1”?
If we could flip the bits appearing after “least significant 1” of original number 101011000 then it looks like 010101000. Now perform binary AND between original number and new number to extract “least significant bit”.
101011000 &
010101000
---------------
000001000
But how do we flip bits appearing after “least significant 1”?
This can be achieved by finding 2s complement of original binary number
2s complement of bValue = 1s complement of bValue + 1
2s complement of 101011000 = ~(101011000) + 1 = 010100111 + 1 = 010101000
Again back to basics, how a negative number is represented?, it's represented as 2's complement of the corresponding positive number.
i.e. for a positive number say 12, its 2's complement is -12.
Now it's more clear, to get new index 8 from 12 by clearing "least significant 1", all we have to do is: (12 - (12 & -12)) = (1100 - (1100 & 0100)) = 1000 = 8
Implementation of 'CumFreq' and running time analysis
Now we know how to clear "least significant 1" from a number, with this we can finish implementation of 'CumFreq'.
int CumFreq(int m) {
int cf = 0;
while (m > 0){
cf += BIT[m];
m = m - (m & -m);
}
return cf;
}
Analysis: The number of times the while loop executes is equal to the number of 1 bits in m.
In worst case which is same as the binary length of the number. The max range is N, if N has all 1 bits then its length is log(N).
Conceptual BIT Tree
The indexing method we discussed above generates a tree within the table of partial frequencies. Below shows the F table and corresponding conceptual BIT tree
Next: Binary Indexed Tree (BIT) Part-3 [Coming soon]
