Sources:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
http://demonstrations.wolfram.com/BinaryIndexedTree/
http://www.algorithmist.com/index.php/Fenwick_tree
Basic Idea:
Given a set of 'n' Elements(Set F), then summarize set-F with a resulting data structure Tree(set T), with the equal number of elements as F.
For Each index in T , T[index] summarizes the information about the elements from 'index-2^r+1' to 'index' in F.
In other words, T[index] is responsible for elements F[index-2^r+1] .....F[index], where 'r' is the position of the last occurance of '1'.
 |
Table of Responsibility
|
 | |
| Table of Responsibilty (Each index'ed element represents range [m,n] |
|
 | |
| Pictorial representation |
Define the Tree:
Now, since we know responsibility of ranges, set 'Tree' can be derived from a defined set 'F'.
 | |
| Pictorial Representation |
How to Implement:
To implement the above idea, we need to follow the below procedures.
1. Find 'r' - i.e the last occurance of '1'.
2. Calulate the range[m,n] for each index based on r of that 'index'.
3. Represent set F as Cumulative frequencies.
4. Build the Tree based on the ranges given. T[index] = C[n]-C[m-1]; where [m,n] is the range covered by index.
5. Supporting required Operations on the implemeted Tree.
a.Read the cumulative frequency.
b.Read the actual frequency.
c.Update the frequency and Update the tree
d.Given a cumulative frequency, find the index. [This is not required As of now]
e.UpScale/Downscale the entire frequencies in the Tree and update tree accordingly. etc.
Finding the Last Digit:
Okay, you are given a number 'N' and we need to find the position of last digit '1'.
representing N in binary format binary(N) = a1b [where 'b' is sequence of 0's and 'a' is sequence of 1's&0's , B is Sequence of all 1's]
representing N'( N's Complement) in binary format binary(N') = (a1b)' +1 = a'1'b'+1 = a'0B +1 = a'1b
N&N' = a1b & a'1b = (0..0)1(0..0) -> Last occurance of '1' is isolated.
Steps - 2,3,4 are easy to implement. At the end of step-4 , building of the BIT would be completed.
BIT should support necessary operations which are useful in range queries, otherwise its useless.
Reading the Cumulative Frequency:
For example, we want to read cumulative frequncy at index=13.
C[13]=C[1101] = Tree[1101] + Tree[1100] + Tree[1000] + T[0000] = 3 + 11 + 12 + 0 = 26;
(i.e. Toggle the 1's from Right to left till the last; T[0000]=0 always coz we never use T[0], we leave that as it is in BITs;)
//psuedoCode:
int readCumulative(int idx){
int sum=0;
while(idx>0){
sum += Tree[idx];
idx -= (idx & -idx);
}
return sum;
}
Reading the Actual Frequency:
Simple approach: Actual frequency can be expressed as below.
F[idx] = C[idx]-C[idx-1];
//psuedoCode:
int readActual(int idx){
return readCumulative(idx) - readCumulative(idx-1);
}
But the complexity will be more(2*O(log maxVal)). So think of an optimal way.
C[13] = C[1101] = Tree[1101] + Tree[1100] + Tree[1000] + T[0000];
C[12] = C[1100] = Tree[1100] + Tree[1000] + T[0000];
Their Trees are matched after 12. So start with sum at idx=13 and substract the nodes till they match.
//psuedoCode:
int readActual(int idx){
int sum = Tree[idx];
if(idx>0){
int z = idx - (idx & -idx);
idx--;
while(idx!=z){
sum -= Tree[idx];
idx -=(idx & -idx);
}
}
}
Update the frequency and Update the tree:
If index 'idx''s frequency is updated , then all the Tree indexes which holds responsibility for this index are have to be updated.[Where ever the r of this idx is toggled.]
//psuedoCode:
void update(int idx,int val){
while(idx <=maxVal){
Tree[idx] += val;
idx += (idx & -idx);
}
}
UpScale/Downscale the entire Tree:upscale/downscale by factor c.
//psuedoCode:
void scale(int c){
for(int i=1;i<=maxVal;i++){
update(i, -(c-1)*readActual(i)/c);
}
}
//or Simple way is
void scale(int c){
for(int i=1;i<=maxVal;i++){
Tree[i] = Tree[i]/c;
}
}
