[Algorithms] Binary Indexed Trees

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

Eg: See the below calculation to find out the range of each index[Max Value of index is 15 here].

Note: Neither set F is defined here nor T is derived here. This calculation is given to explain how ranges are considered at each Index of the Tree.

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