May 12, 2015

Binary Indexed Tree (BIT) Part-2


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.

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 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 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

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.

Let's explore how we can find cumulative frequency at index/number j. To find the cumulative frequency at index 12 (F[1] + F[2] + .. + F[12]), just considering value at BIT[12] is not sufficient as it contains only sum from F[9] to F[12]. We need to find the sum of frequencies from F[1] to F[8] and add it to BIT[12] to get cumulative frequency.

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]


Iterating through indices (12 -> 8 -> 0) to find accumulative frequency

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




Conceptual BIT Tree



 Next: Binary Indexed Tree (BIT) Part-3 [Coming soon]
at No comments:

Binary Indexed Tree (BIT) Part-1



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 first 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 1


Consider a frequency table F, that stores frequencies of numbers in the range [1...N].  Such a table can be represented using a one dimensional array.

F[i], 1 <= i <= N
F[i] stores frequency of number i.

In this representation frequency of a number i is stored at index i, this defines a one-to-one mapping between number and index.

Below is a sample frequency table F storing frequencies of number in the range [1..16]






 For example element at index 5 stores frequency of number 5, which is 8.

Since we use number itself as table index and since the numbers ranges from 1 to N, we will not use 0th index of the table.

The problem we are trying to solve is - given such a table, we want answer following type of queries:

Query #1: Find cumulative frequency at a number m inclusive.
  int CumFreq(m)

Query #2: Update frequency of a number m by x.
  void Update(m, x)

Query #3: Find/Read frequency of a number m.
  int Read(m)

Query #4: Find a number with given frequency f.
  int FindByFrequency(f)

Naive apporach 1: Using F table


Since table F is an array which is indexed using number,  type  #2 and #3 queries can be answered in O(1) time.

#2 Update the frequency of number m by x
  Action<in, int> Update = (m, x) => { F[m] + x; }

#3 Read frequency of a number
  Func<int> Read = (m) => { return F[m]; }

The cumulative frequency at a number m can be calculated by adding the frequency of number m to the cumulative frequency of the previous number m - 1. The cumulative frequency for the number 1 is same as its frequency since there is no cumulative frequency before it.

By just using frequency table F, achieving #1 requires iterating through the table from 1 to m

             i=m  
CF(m) = Σ F(i)
             i=1

Func<int> CumFreq = (m) => {
 int cf = 0;
 for (int i = 1; i <= m; i++) { cf += F[i]; }
 return cf;
};

Using this method to find the cumulative frequency takes O(N).

Naive approach 2: Using CF table

Another approach is maintaining a table CF, where CF[j] stores the cumulative frequency at number j.












This approach will take O(N) time for pre-computing the CF table. 
The value stored at index j of table CF is:

            j  
CF(j) = Σ F[a]
           a=1

Using CF table type #1 and #3 queries can be answered in O(1).

#1 Cumulative frequency at number m

Func<int> CumFreq = (m) => { return CF[m]; }

#3 Find frequency of a number m
Func<int> Read = (m) => {
 if (m == 1) { return CF[m]; }
 return CF[m] - CF[m - 1];
}

#2 type queries takes O(N) in this case. Updating frequency of a number m by x requires adding x to cumulative frequency of all numbers following m, inclusive.

Action<int, int> Update = (m, x) => {
 for (int i = m; i < CF.Length; i++) { CF[i] += x; }
};

Comparison of naive approaches with BIT

Before we start exploring BIT, let’s compare running time of above two naive approach with upcoming BIT approach so we know what BIT guarantee.

Query
Using F table
Using CF table
Using BIT
int Read(int m)
O(1)
O(1)
O(log(N))
void Update(int m, int x)
O(1)
O(N)
O(log(N))
int CumFreq(int m)
O(N)
O(1)
O(log(N))




Notes:
  1. [1..N] is the range of numbers whose frequencies we are manipulating.
  2. N is the max value for ‘number’
  3. 1 <= m <= N


at No comments: